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

Question

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

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

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

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

Answer 1

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

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

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

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