эффективный алгоритм для поиска пути минимальной стоимости

Question

Существует определенный набор городов, позволяющих говорить .. A, B, C, D, E, F, G. Проблема заключается в том, чтобы найти путь минимальной стоимости, который охватывает города A, B, C, F. Очень важно, чтобы путь охватывал города A, B, C, F. Путь может (но не обязательно) проходить через любой из других городов (D, E, G). Разрешается повторение пути. Путь должен начинаться и заканчиваться на A. Как я должен решить проблему вдоль подобных линий?

Answer 1

Это вариант Travelling Salesman Problem (TSP) в маскировке.

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

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

Во-первых, предвычисления кратчайших путей между интересными городами. Это можно сделать с помощью Dijkstra's algorithm от любого интересного города или Floyd-Warshall algorithm. Затем либо попробуйте каждую перестановку порядка посещения интересных городов; или использовать какой-либо существующий решатель TSP или эвристический алгоритм.

Так Простейшая реализация выглядит следующим образом:

1. Применить Floyd-Воршалла в городе графике. Это намного проще реализовать, чем Dijkstra's. Я нашел хороший PDF с их сравнением. Он получает матрицу со всеми кратчайшими путями для AB, AC, AF, BC, BF и CF. Если вам нужно получить фактический путь, как в последовательности городов, посмотрите на Path reconstruction section в Википедии.
2. Попробуйте каждую перестановку порядка посещения интересных городов, кроме A (т. Е. Только B, C и F). Если вы используете C++, Python или Ruby, они имеют функцию перестановки в стандартной библиотеке. Для других языков вы можете использовать стороннюю библиотеку или выполнить поиск стека для алгоритма.
3. Найти перестановку с наименьшей общей стоимостью пути. Например, для перестановки C-F-B общая стоимость составляет AC + CF + FB + BA. У вас уже есть все эти значения от Floyd-Warshall, поэтому вы можете просто их суммировать.

Если у вас есть V всего города и N интересные города, среда выполнения этой реализации будет составлять около O (V + N! · N)