Вариация TSP, которая посещает несколько городов

Question

Я хочу обсудить отраслевое и привязанное решение для TSP с несколькими посещениями.(то есть каждый город нужно посетить по крайней мере один раз, а не только один раз)

Редактировать:

Устранил сомнение, поскольку это не было релевантно, как указал Джитсе.Теперь вопрос более ясен.

Answer 1

Просто дополните график, добавив для каждой пары узлов A и B ребро, представляющее кратчайший путь от A до B.В Алгоритм Флойда-Варшалла позволяет вам сделать это за O (n ^ 3), что намного быстрее любого алгоритма TSP.Как только вы сделаете это, используйте стандартную технику ветвления и привязки TSP. Этот сайт имеет некоторую информацию от Книга Эпплгейта, в котором обсуждается ветвление и граница для TSP в соответствии с Запись TSP в Википедии.

Answer 2

Я бы предпочел представить это как комментарий к ответу Мартина Хока, потому что я обращаюсь к возможному упущению, которое было бы легко осуществить, реализуя его предложение.

Алгоритм ветвления и привязки необходимо объединить с алгоритмом восстановления путей с наименьшими затратами, учитывая выходные данные алгоритма Флойда-Варшалла.Алгоритм ветвления и привязки является внешним циклом, и он выбирает непросмотренные узлы.Затем вы используете алгоритм восстановления пути с наименьшими затратами, чтобы фактически добавить ребра и узлы в свой цикл.Узлы должны быть помечены как посещенные алгоритмом восстановления пути с наименьшими затратами, а не только частью ветвления и привязки.