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