java — реализация определенного варианта коммивояжера
Я ищу алгоритм (C / C ++ / Java — не имеет значения), который решит проблему, состоящую в поиске кратчайшего пути между 2 узлами (A и B) графа. Подвох в том, что путь должен посещать определенные другие заданные узлы (города). Город можно посетить не раз. Пример пути (-Н-Д-С-Е-F—г—F—В) (где A — источник, B — пункт назначения, F и G — города, которые необходимо посетить).
Я рассматриваю это как вариант задачи коммивояжера, но не могу найти или написать работающий алгоритм, основанный на моих поисках.
Я пытался найти решение, начиная с этих тем, но безуспешно:
https://stackoverflow.com/questions/24856875/tsp-branch-and-bound-implementation-in-c а также
Вариация TSP, которая посещает несколько городов
Решение
Простое сокращение проблемы до TSP будет:
- Для каждого
(u,v)что «надо посетить», найдите расстояниеd(u,v)между ними. Это можно сделать эффективно, используя Алгоритм Флойда-Варшалла найти кратчайший путь для всех. - Создайте новый граф G ‘, состоящий только из этих узлов, со всеми существующими ребрами, с расстояниями, рассчитанными по (1).
- Запустите стандартный алгоритм TSP для решения задачи на приведенном графе.
Другие решения
Я думаю, что в дополнение к ответу amit, вы захотите увеличить стоимость ребер с A или B в качестве конечных точек на достаточную величину (общая стоимость графика + 1, вероятно, будет достаточно), чтобы гарантировать, что вы надеваете не заканчивается путь, который проходит через A или B (вместо того, чтобы заканчиваться в A и B).
A--10--X--0--B
| | |
| 10 |
| | |
+---0--Y--0--+
Приведенный выше случай приведет к пути от A до Y к B к X, если только вы не увеличите стоимость ребер A и B (на 21).
A--31--X--21--B
| | |
| 10 |
| | |
+---21--Y--21-+
Теперь он идет от А к Х к Y к Б.
Также убедитесь, что вы удалили все ребра (A, B) (если они существуют).