Форум программистов, компьютерный форум, киберфорум
Наши страницы
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
skiminock
2 / 2 / 1
Регистрация: 11.06.2012
Сообщений: 18
1

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

04.03.2014, 13:48. Просмотров 759. Ответов 1
Метки нет (Все метки)

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

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

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

про отображение самой карты вопрос не стоит) Спасибо за внимание)
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.03.2014, 13:48
Ответы с готовыми решениями:

Нахождение кратчайшего расстояния и пройденного расстояния по траектории движения мыши
Здравствуйте, необходимо найти кратчайшее расстояние и пройденное расстояние по...

Поиск кратчайшего пути
Саша и Маша путешествуют вдоль оси Ох на которой есть (неизвестное кол-во)...

Поиск кратчайшего пути
В одном массиве даны все возможные комбинации чисел (0,1,2,3,4). Представляют...

Поиск кратчайшего пути в матрице
Привет всем, есть задание: "Считать из файла input3.txt двумерный массив....

Поиск кратчайшего маршрута между населенными пунктами
Написать програму поиска кратчайшего маршрута между населенными пунктами.

1
kolorotur
Эксперт .NET
10483 / 8670 / 2157
Регистрация: 17.09.2011
Сообщений: 14,887
Завершенные тесты: 1
04.03.2014, 14:11 2
Лучший ответ Сообщение было отмечено tezaurismosis как решение

Решение

Цитата Сообщение от skiminock Посмотреть сообщение
1) В каком виде хранить карту? (я так понимаю, что нужно хранить в виде дерева и применить, например, алгоритм Дейкстры для поиска)
Только не дерева, а графа.
Алгоритм Дейкстры вполне пойдет для учебного задания или карты с небольшим количеством вершин/ребер, но для реальных систем (напр., навигационный софт) неприемлем.

Цитата Сообщение от skiminock Посмотреть сообщение
2) Что брать за вершины графа - пересечения улиц? м?
Пересечение дорог, которые принимают участие в высчитывании пути.

Цитата Сообщение от skiminock Посмотреть сообщение
3) Какой другой алгоритм поиска можете посоветовать?
На вики перечислено несколько методов, используемых в навигационных системах.

Цитата Сообщение от skiminock Посмотреть сообщение
4) Как заполнять такой граф, если не рандомом, а именно строить карту какого либо РЕАЛЬНОГО города?
Зависит от того, в каком виде поставляется карта дорожной сети.
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.03.2014, 14:11

Поиск адреса на карте
Интересует вопрос реализации. Как можно сделать так, что бы при вводе адреса в...

Поиск минимального расстояния среди 3 точек
Разработать метод f(x1, y1, x2, y2), который вычисляет длину отрезка по ...

Поиск расстояния между заданными символами
Мне нужна найти ростояния n - символов в слове. Например есть текст: Человек ек...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru