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

Question

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

Edit:

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

Answer 1

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

Answer 2

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

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