Алгоритм поиска мимимального пути

[Санька]

Доброго времени суток, господа форумчане.

Заинтересовала тема ГИС, и соответственно вопрос - как ПРАКТИЧЕСКИ реализуется алгоритм минимального поиска пути, применительно к карте!??!
Погуглил, нашёл множество алгоритмов по этому поводу (на графах и прочие), но как именно ПРАКТИЧЕСКИ алгоритм реализуется и применяется я не нашёл.....буду очень благодарен за помощь.

[Boris]

Ответ на этот вопрос занимает несколько разделов математики и несколько разных расширений в ArcGIS. Надо как-то определится с более точной постановкой задачи ил вопроса.

[Санька]

Моя сегодняшняя цель - сделать по быстрее дипломную работу, чтобы потом не отвлекаться от того, чем я буду заниматься в будущем.
Тема - алгоритм поиска минимального пути с использованием GPS навигаторов. Соответственно выбор алгоритмов, описание достоинств и недостатков и на проведённых выводах - реализация его.

[Boris]

Боюсь, что к поиску кратчайшего пути GPS навигатор имеет такое же отношение как "барышня" в справочном окошке к поиску информации о времени работы учреждения или адресе. Ответ только один - они это делают. Как реализован это внутренний алгоритм, это другая задача. Сам GPS навигатор, причем именно навигатор, а не приемник, ее успешно решает. Для того, что бы описать как "с помощью GPS-навигатора" ищется кратчайший путь сами алгоритмы знать и не надо, надо просто указать, что в основном - только двумя способом:
а) тыкают на карте начало и конец пути
б) набирают то же самое на клавиатуре
---
Что же до самих алгоритмов, то это алгоритмы на графах. Причем учитывая достаточно высокую скорость расчетов пути, часть путей уже предвычислена. Алгоритмов поиска кратчайшего пути не слишком много. Много их вариантов. К тому же я что-то не знаю открытых GPS-навигаторов, в которых открыты алгоритмы поиска пути, а самое главное их оптимизации и упаковки. Так, что тут то же не понятно как именно их сравнивать.

[bim2010]

Литература по алгоритмам
Кормен Т. Лейзерсон Ч. Ривест Р. Штайн К.Алгоритмы построение и анализ - лучшая на мой взгляд книга.

Седжвик Роберт Фундаментальные алгоритмы на C++. Алгоритмы на графах
Таха Х.А. Введение в исследование операций
Кристофидес Н. Теория графов
Окулов С.М. Программирование в алгоритмах
Грешилов А.А. Прикладные задачи математического программирования
Зубов В.С. Справочник программиста. Базовые методы решения графовых задач и сортировки.
http://www.studzona.com/referats/view/11139


Литература по GPS:
Guochang Xu GPS. Theory, Algorithms and Applications.
Б. К. Леонтьев GPS: Все, что Вы хотели знать, но боялись спросить
Яценков В.С. Основы спутниковой навигации Системы GPS NAVSTAR и ГЛОНАСС
Ю.А. Соловьев Системы спутниковой навигации
М.М. Маковеева Ю.С. Шинаков Системы связи с подвижными объектами
В.Н. Харисова А.И. Перова В.А. Болдина Глобальная спутниковая радионавигационная система
Б.Б. Серапинас Глобальные системы позиционирования
КВАЛИФИКАЦИОННЫЕ ТРЕБОВАНИЯ КТ-34-01 «Бортовое оборудование спутниковой навигации»
Генике А.А. Побединский Г.Г. Глобальные спутниковые системы определения местоположения и их применение в геодезии


Алгоритмы:

Boost Graph Library
http://www.boost.org/doc/libs/1_38_0/li ... tents.html
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
http://ru.wikipedia.org/wiki/%D0%94%D0% ... 0%B1%D0%B5
http://www.en.giswiki.org/wiki/Algorithmus_von_Dijkstra
http://www.tarikattar.com/blog/
http://en.wikipedia.org/wiki/A*_search_algorithm
http://theory.stanford.edu/~amitp/GameProgramming/

Посмотрите еще это:
Плагин умеет вычислять кратчайшие расстояния по дорожному графу, использует алгоритм Дейкстры.
viewtopic.php?f=27&t=3262&st=0&sk=t&sd=a&start=15

pgRouting
http://pgrouting.postlbs.org/wiki/Works ... G2008/ch02
http://en.giswiki.net/wiki/PostLBS

Quantum Navigator
http://blog.qgis.org/?q=node/73
http://mapserver.sk/~wonder/qnavigator/
http://www.keittlab.org/node/160

Алгоритмы и методы решения задач составления расписаний и других экстремальных задач на графах больших размерностей
http://www.emis.de/journals/FPM/ps/k03/k031/k03114.pdf

http://webfea.fea.aub.edu.lb/proceeding ... ECE-27.pdf
http://www.sjabbar.com/GPSbasedNavigation.ppt
http://lyle.smu.edu/~rewini/3358/F05/gps.ppt
http://mainline.brynmawr.edu/Courses/cs ... kstra).pdf
http://www.nomagicsmoke.com/projects/20 ... jkstra.pdf
http://www.apan.net/meetings/honolulu20 ... ing-Su.pdf

Ну и по логистике несколько книг

Неруш Ю.М. Логистика

Аникин Б.А. Логистика
Практикум по логистике
В.С. Лукинский Логистика автомобильного транспорта
Официальный сайт Лукинского Валерия Сергеевича
http://www.luka.adviss.ru/content/category/3/6/20/

Я использую алгоритм Дейкстра - очень бысто работает. Но похоже одного алгоритма Вам будет не достаточно.
Успеха !

[dimas4]

а pgrouting кто нибудь юзал? или документацию на русском с примерами находил?

[JEY]

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