Как решить проблему Модифицированного коммивояжера?

Question

Классическая задача коммивояжера о том, что вы можете посетить каждый узел ровно один раз.

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

Т.е. график

1-2-3 (в треугольнике. масса ненаправленного края: 1-2 1

1-3 1

3-2 500

Лучший путь - от 1 до 2, затем до 1, затем до трех.

Алгоритм для решения этой проблемы я не могу понять. Если использовать обычный tsp, это приведет к бесконечным циклам.

Answer 1

Вы можете просто заменить расстояния на расстояния с кратчайшим путем между каждой парой узлов.Таким образом, в вашем примере, расстояния будут: 1-2: 1 1-3: 1 2-3: 2 Тогда вы решите обычный TSP в этом случае.Модель «думает», что посещает каждый город только один раз, хотя один из краев фактически проводит его «через» город во второй раз.