Алгоритм Дийсктра, применяемый к задаче коммивояжера

Я новичок (абсолютный новичок в теории вычислительной сложности), и у меня есть вопрос.

Допустим, у нас есть «проблема коммивояжера», решит ли ее следующее применение алгоритмов Дейкстры?

Из начальной точки мы вычисляем кратчайшее расстояние между двумя точками. Мы идем к сути. Удаляем исходную точку. Затем мы вычисляем следующую кратчайшую точку расстояния от текущей точки и так далее ...

С каждым шагом мы уменьшаем график, пока перемещаем следующую доступную кратчайшую точку расстояния. Пока мы не посетим все точки.

Это решит проблему коммивояжера?

Алгоритм Дейкстры возвращает дерево кратчайших путей, содержащее кратчайший путь от начальной вершины до каждой другой вершины, но не обязательно кратчайшие пути между другими вершинами, или кратчайший путь, который посещает все вершины.

Вот контрпример, где описанный вами жадный алгоритм не будет работать:

Начиная с , жадный алгоритм будет выбирать маршрут , но самый короткий маршрут, начинающийся и заканчивающийся в равен . Поскольку маршрут TSP не может повторять вершины, как только жадный алгоритм выбирает , он вынужден взять самый длинный край чтобы вернуться в начальный город.[ a , b , c , d , a ] a [ a , b , d , c , a ] a , b , c , d d , $a$$[a,b,c,d,a]$$a$$[a,b,d,c,a]$$a,b,c,d$$d,a$

Как уже выяснилось в других ответах, ваше предложение не позволяет эффективно решить проблему коммивояжера, позвольте мне указать лучший способ, известный в области эвристического поиска (поскольку я вижу алгоритм Дейкстры, в некоторой степени связанный с этой областью искусственного интеллекта) ,

Эвристический алгоритм может возвращать оптимальные решения (хотя размеры, которыми он может управлять, на самом деле относительно малы), и в 90-х годах Ричард Корф предложил следующий метод. Хотя он отлично работает для задачи симметричного коммивояжера (где стоимость ребра равна стоимости того же ребра при прохождении в противоположном направлении ), его можно легко адаптировать к альтернативному случай асимметричной версии.( V , U $(u,v)$$(v,u)$

Лучший подход (насколько мне известно) состоит в запуске алгоритма эвристического поиска с первым углублением по ветвям и границам , где эвристика представляет собой стоимость минимального связующего дерева (MST). Поскольку MST может быть вычислена за полиномиальное время либо с алгоритмом Прима или алгоритма Крускала , то можно ожидать возвращения решения в разумные сроки. Для прекрасного обсуждения этих двух алгоритмов я настоятельно рекомендую вам взглянуть на Руководство по разработке алгоритмов.

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

Надеюсь это поможет,

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

Ответ - нет, это не очень хороший способ решения проблемы TSP. Хороший пример счетчика - это когда все точки находятся на одной линии, например:

--5 ------------------ 3 ----- 1--0 --- 2 ---------- 4

используя алгоритм Dijsktra, заставил бы плохого продавца начать с точки 0, сначала перейти к 1, затем к 2, затем к 3 и т. д. что не является оптимальным.

Надеюсь, это поможет. Взгляните на первую главу превосходной книги Стивена С. Шиена под названием «Разработка алгоритма», в которой этот пример объясняется более подробно.

Проблема TSP заключается не в поиске кратчайшего пути между двумя точками, а в создании маршрута между всеми точками, которые являются оптимальными. Когда у вас есть оптимальный маршрут, вы можете использовать Dijsktra, чтобы найти кратчайший путь между каждой точкой маршрута.