|
Необходимо пройти все вершины графа. С помощью алгоритма дейкстры, я могу найти только минимальное расстояние от одного города до всех остальных.
Далее я хочу проложить маршрут через все точки. Для этого, допустим, я вычислил минимальные расстояния от каждого города , до любого другого. Т.е. получилась матраца расстояний. 2. Как с помощью этой матрицы проложить кратчайший маршрут? задан 22 Май '13 18:14 
sobaka-muhtar
показано 5 из 6
показать еще 1
|
|
Алгоритм Дейкстры имеет полиномиальную сложность. Если бы с его помощью можно было реализовать алгоритм полиномиальной сложности для нахождения полугамильтонова маршрута, или варианта задачи коммивояжёра, то имело бы смысл обратиться в Институт Клэя за премией в миллион долларов :) Добавление. Можно оставить в стороне алгоритм Дейкстры, и рассмотреть такую задачу. Дано $%n$% точек на евклидовой плоскости, расположенных в узлах целочисленной решётки. Матрица расстояний между точками тем самым уже дана -- это обычные евклидовы расстояния, измеряемые по линейке. Их точные значения известны, если применить теорему Пифагора. Тем не менее, задача построения кратчайшего маршрута, проходящего через все эти точки (во всех разумных вариантах), осуществляемого за полиномиальное время, также относится к категории NP-полных задач. То, что зная все расстояния, легко построить требуемый путь -- это иллюзия. отвечен 22 Май '13 19:58 
falcao |
Если требуется проложить кратчайший маршрут, проходящий через все точки, то это задача коммивояжёра. Она при помощи алгоритма Дейкстры не решается.
Расстояния мы можем узнать при помощи алгоритма Дейкстры, но тогда в чём заключается сам вопрос, если это не маршрут коммивояжёра? Что нужно построить в конечном итоге? Желательно описать точно свойства требуемого маршрута или чего-то ещё.
Кратчайший маршрут из всех точек, без возвращения в первоначальную точку
Но это один из вариантов задачи коммивояжёра, относящийся к классу NP-полных задач. То же самое относится и к задаче нахождения полугамильтонова маршрута, то есть без возврата в начальную точку.
Можете объяснить почему нельзя?Я же с его помощью могу составить матрицу расстояний от каждого города до каждого. Т.е. могу найти расстояние миним до 2ой вершины, затем минимльное до третьей вершины и т.д.
Я преобразовал свой комментарий в ответ, потому что тут не осталось больше места для дополнительных комментариев. Дело вот в чём: на данный момент никто не умеет не только находить "быстрый" (за полиномиальное время) алгоритм решения NP-полных задач, но и отсутствие такого алгоритма тоже является открытым вопросом. Если бы кто-то умел доказывать, что такого алгоритма не имеется в принципе, то это было бы решением одной из "проблем миллениума". Но я предлагаю поступить проще, о чём сейчас напишу в добавлении к ответу (тут уже место кончилось).