Необходимо пройти все вершины графа.

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

  1. Как узнать, через какие вершины проходит этот минимальный путь?

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

задан 22 Май '13 18:14

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

(22 Май '13 18:26) falcao

Расстояния мы можем узнать при помощи алгоритма Дейкстры, но тогда в чём заключается сам вопрос, если это не маршрут коммивояжёра? Что нужно построить в конечном итоге? Желательно описать точно свойства требуемого маршрута или чего-то ещё.

(22 Май '13 18:58) falcao

Кратчайший маршрут из всех точек, без возвращения в первоначальную точку

(22 Май '13 19:03) sobaka-muhtar

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

(22 Май '13 19:21) falcao

Можете объяснить почему нельзя?Я же с его помощью могу составить матрицу расстояний от каждого города до каждого. Т.е. могу найти расстояние миним до 2ой вершины, затем минимльное до третьей вершины и т.д.

(22 Май '13 20:03) sobaka-muhtar

Я преобразовал свой комментарий в ответ, потому что тут не осталось больше места для дополнительных комментариев. Дело вот в чём: на данный момент никто не умеет не только находить "быстрый" (за полиномиальное время) алгоритм решения NP-полных задач, но и отсутствие такого алгоритма тоже является открытым вопросом. Если бы кто-то умел доказывать, что такого алгоритма не имеется в принципе, то это было бы решением одной из "проблем миллениума". Но я предлагаю поступить проще, о чём сейчас напишу в добавлении к ответу (тут уже место кончилось).

(22 Май '13 20:13) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
0

Алгоритм Дейкстры имеет полиномиальную сложность. Если бы с его помощью можно было реализовать алгоритм полиномиальной сложности для нахождения полугамильтонова маршрута, или варианта задачи коммивояжёра, то имело бы смысл обратиться в Институт Клэя за премией в миллион долларов :)

Добавление. Можно оставить в стороне алгоритм Дейкстры, и рассмотреть такую задачу. Дано $%n$% точек на евклидовой плоскости, расположенных в узлах целочисленной решётки. Матрица расстояний между точками тем самым уже дана -- это обычные евклидовы расстояния, измеряемые по линейке. Их точные значения известны, если применить теорему Пифагора. Тем не менее, задача построения кратчайшего маршрута, проходящего через все эти точки (во всех разумных вариантах), осуществляемого за полиномиальное время, также относится к категории NP-полных задач. То, что зная все расстояния, легко построить требуемый путь -- это иллюзия.

ссылка

отвечен 22 Май '13 19:58

изменен 22 Май '13 20:20

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×560

задан
22 Май '13 18:14

показан
2360 раз

обновлен
22 Май '13 20:20

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru