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

Question

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

Answer 1

Это замаскированный вариант задачи коммивояжера.

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

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

Во-первых, заранее рассчитать кратчайшие пути между интересными городами. Это можно сделать с помощью алгоритма Дейкстры из любого интересного города или алгоритма Флойда-Варшалла. Тогда либо попробуйте каждую перестановку порядка посещения интересных городов; или использовать какой-либо существующий решатель TSP или эвристический алгоритм.

Итак, простейшая реализация выглядит так:

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

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