Поиск кратчайшего расстояния на карте города

@skiminock · Регистрация: 11.06.2012

Author24 — интернет-сервис помощи студентам

Здравствуйте! Есть задание : "Найти наикратчайший путь между двумя точками на карте ГОРОДА"

Возникли вопросы:

1) В каком виде хранить карту? (я так понимаю, что нужно хранить в виде дерева и применить, например, алгоритм Дейкстры для поиска)
2) Что брать за вершины графа - пересечения улиц? м?
3) Какой другой алгоритм поиска можете посоветовать?
4) Как заполнять такой граф, если не рандомом, а именно строить карту какого либо РЕАЛЬНОГО города?

про отображение самой карты вопрос не стоит) Спасибо за внимание)

@kolorotur · 04.03.2014, 14:11

Сообщение от skiminock

1) В каком виде хранить карту? (я так понимаю, что нужно хранить в виде дерева и применить, например, алгоритм Дейкстры для поиска)

Только не дерева, а графа.
Алгоритм Дейкстры вполне пойдет для учебного задания или карты с небольшим количеством вершин/ребер, но для реальных систем (напр., навигационный софт) неприемлем.

Сообщение от skiminock

2) Что брать за вершины графа - пересечения улиц? м?

Пересечение дорог, которые принимают участие в высчитывании пути.

Сообщение от skiminock

3) Какой другой алгоритм поиска можете посоветовать?

На вики перечислено несколько методов, используемых в навигационных системах.

Сообщение от skiminock

4) Как заполнять такой граф, если не рандомом, а именно строить карту какого либо РЕАЛЬНОГО города?

Зависит от того, в каком виде поставляется карта дорожной сети.

@skiminock 2 / 2 / 1 Регистрация: 11.06.2012 Сообщений: 18
		1
	Поиск кратчайшего расстояния на карте города 04.03.2014, 13:48. Показов 1791. Ответов 1 Метки нет (Все метки) Здравствуйте! Есть задание : "Найти наикратчайший путь между двумя точками на карте ГОРОДА" Возникли вопросы: 1) В каком виде хранить карту? (я так понимаю, что нужно хранить в виде дерева и применить, например, алгоритм Дейкстры для поиска) 2) Что брать за вершины графа - пересечения улиц? м? 3) Какой другой алгоритм поиска можете посоветовать? 4) Как заполнять такой граф, если не рандомом, а именно строить карту какого либо РЕАЛЬНОГО города? про отображение самой карты вопрос не стоит) Спасибо за внимание) 0

@kolorotur 17685 / 12871 / 3365 Регистрация: 17.09.2011 Сообщений: 21,136
	04.03.2014, 14:11	2
	Сообщение было отмечено tezaurismosis как решение Решение Сообщение от skiminock 1) В каком виде хранить карту? (я так понимаю, что нужно хранить в виде дерева и применить, например, алгоритм Дейкстры для поиска) Только не дерева, а графа. Алгоритм Дейкстры вполне пойдет для учебного задания или карты с небольшим количеством вершин/ребер, но для реальных систем (напр., навигационный софт) неприемлем. Сообщение от skiminock 2) Что брать за вершины графа - пересечения улиц? м? Пересечение дорог, которые принимают участие в высчитывании пути. Сообщение от skiminock 3) Какой другой алгоритм поиска можете посоветовать? На вики перечислено несколько методов, используемых в навигационных системах. Сообщение от skiminock 4) Как заполнять такой граф, если не рандомом, а именно строить карту какого либо РЕАЛЬНОГО города? Зависит от того, в каком виде поставляется карта дорожной сети. 2

Поиск кратчайшего расстояния на карте города

Решение