Алгоритм: кратчайший маршрут между 10 городами

У меня есть график с 80 городами. Мне нужно найти кратчайший маршрут, проходящий через 10 городов.

Я должен начать с города, который уже определен как начальный город, и пользователь введет 10 названий городов из списка городов. Я должен путешествовать по этим 10 городам, а затем я должен вернуться в город, где я начал. У меня просто есть вся информация о дорожных расстояниях между соседними городами. У меня нет никакой информации, кроме этой.

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

Могу ли я использовать Dijkstra для кратчайшего пути между стартовым городом и другими 10 городами, а затем найти минимальное остовное дерево этого и пройти по нему? Есть ли какой-нибудь эвристический алгоритм, который я могу использовать с этими данными?

Всего 1 ответ


Учитывая ваши 10 городов, найдите кратчайший путь между каждой парой. Это всего 45 вызовов алгоритма Дейкстры. Это дает вам полный граф на 10 вершин.

Теперь у вас есть проблема с коммивояжером, но 10 городов - не так много, и вам дан стартовый город, так что всего 9! (362880) возможностей. Я просто попробую все перестановки и найду минимальную.

Вы можете сделать что-то умнее, но это простое грубое решение будет быстрым и простым в коде.

[править: возможно у вас есть стартовый город и 10 других городов. Тем не менее, 10! (3728800) достаточно мал для быстрого поиска каждой перестановки]


Есть идеи?

10000