Во отсутствие обсуждения, покритикую себя сам.
Совершенно понятен недостаток предложенного выше рекурсивного алгоритма, как аналога алгоритма решения задач человеческим интеллектом. Когда человек решает задачу, он не пытается сразу проработать все детали всего плана до конца, т.е. не пытается составить план решения вплоть до сокращений конкретных мышц для каждого пункта плана (для каждой подзадачи). Человек прорабатывает план максимально детально только от первого пункта до второго пункта. При достижении второго пункта - прорабатывает детали между вторым и третьим пунктом и так далее.
С учётом этого соображения полностью идеологически переделал алгоритм и теперь он решает 1000 узлов за 3 секунды. И результат при этом показывает на несколько процентов лучший.
Решение задачи коммивояжёра рекурсивным жадным алгоритмомУсловия задачи
те же, что и ранее.
Для синтеза плана решения задачи возьмём за основу 2 соображения.
1. Кратчайший путь между двумя точками на плоскости в метрике евклида всегда лежит по прямой.
2. Самые дальние узлы вносят наибольшую ошибку в суммарную длину маршрута если эти дальние узлы не самым лучшим образом соединены с остальными узлами.
Исходя из этих двух соображений построим алгоритм таким образом.
1. Соединим входной и выходной узел отрезком прямой. Этот итоговый маршрут из Вх в Вых будет, очевидно, кратчайшим.
2. Однако у нас в задаче есть, к сожалению, и другие узлы, которые тоже должны быть включены в итоговый маршрут. Поэтому мы постараемся минимальным образом ухудшать этот наилучший кратчайший маршрут и будем по одному включать в него остальные узлы.
3. Для этого, из всех оставшихся узлов (в силу второго нашего соображения) мы выберем взаимо-дальний узел к первоначальным двум (Вх и Вых) и включим его в найденный кратчайший маршрут оптимальным образом - разорвём связь между Вх и Вых и соединим Вх и Вых через этот третий взаимо-дальний узел.
4. Далее найдём взаимо-дальний узел к первым трём узлам и включим его в итоговый маршрут таким образом, чтобы это включение дало минимальный прирост длины маршрута. Ясно, что при включении этого четвёртого узла у нас появится выбор из двух рёбер (для третьего узла такого выбора не было). Поэтому здесь и далее нам придётся для каждого нового взаимо-дальнего узла перебирать все рёбра текущего полученного маршрута и выбирать из этих рёбер то, разрыв которого даст минимальный прирост длины.
5. Точно так же поступим с оставшимися узлами.
Программу и исходники можно скачать
здесь. (Поменял немного интерфейс, теперь окно можно растягивать.)
Достоинства алгоритма:
1. Простота.
2. Скорость. На машине с четырёх-ядерным процессором 2,67 ГГц
1000 узлов - 3 секунды
2000 узлов - 27 секунд
3000 узлов - 87 секунд
4000 узлов - 207 секунд
Прирост времени экспоненциальный, но для практических задач достаточно медленный.
3. В сравнении с ранее предложенным рекурсивным алгоритмом результат получается лучшим примерно на 8%.
4. Минимальное использование оперативной памяти.
5. Отсутствие каких-либо настроек.
6. Минимальное количество пересечений без какой-либо проверки на пересечения.
UPD: Подправил в программе глюк с сообщениями в WinXP.