В предыдущей публикации был рассмотрен алгоритм решения задачи коммивояжёра на плоскости рекурсивным полным перебором. Результат получился любопытным, но итоговый маршрут содержал очевидные неоптимальные участки. В предлагаемой заметке рассмотрен улучшенный алгоритм, который я назвал «рекурсивным жадным алгоритмом». Признаюсь сразу, итоговый маршрут в сравнении с рекурсивным полным перебором получается лучше, в среднем, на 8%.
Читать полностью »
Метка «задача коммивояжёра»
Решение задачи коммивояжёра на плоскости рекурсивным жадным алгоритмом
2012-09-21 в 16:26, admin, рубрики: Алгоритмы, задача коммивояжёра, ненормальное программирование, Программирование, рекурсия, метки: задача коммивояжёра, рекурсияРешение задачи коммивояжёра рекурсивным полным перебором
2012-09-10 в 9:13, admin, рубрики: задача коммивояжёра, Песочница, полный перебор, рекурсия, метки: задача коммивояжёра, полный перебор, рекурсия Сформулируем задачу.
Дано N узлов, расположенных на плоскости. Задан входной узел (Вх) и выходной узел (Вых). Необходимо обнаружить кратчайший путь, охватывающий все узлы, начинающийся во входном узле, заканчивающийся в выходном узле и проходящий через каждый узел только один раз.
Есть мнения, что задача коммивояжёра может формулироваться ещё двумя способами:
1. Необходимо обнаружить кратчайший гамильтонов цикл.
2. Необходимо обнаружить кратчайший путь, начинающийся в заданном узле.
Однако обе эти формулировки при ближайшем рассмотрении оказываются частными случаями первоначальной формулировки.
Формулировка 1 подразумевает, что входным узлом может быть любой узел, а выходным — один из ближайших к нему. Что требует полного перебора всех ближайших узлов к произвольно выбранному узлу.
Формулировка 2 подразумевает, что входной узел задан, а выходным узлом может быть любой. Что требует полного перебора всех выходных узлов с последующим выбором кратчайшего пути из всех кратчайших.
Поэтому мы остановимся на первоначальной формулировке, и будем решать задачу в общем виде.
Читать полностью »