Используется ли алгоритм Дейкстры в современных системах поиска маршрутов?

10

Используется ли алгоритм Дейкстры в современных системах поиска маршрутов, таких как карты Google или спутниковая навигация в вашем автомобиле? Если нет, то что?

algorithms graphs shortest-path applied-theory тяпка ничья lion4
источник
Я предполагаю, что вы имеете в виду компонент маршрутизации, который находит ваш путь, как только GPS, который в первую очередь является системой глобального позиционирования , определил, где вы находитесь . Еще один случай, когда хвост виляет собакой.
Бабу
1
Я не могу дать источник для этого, но мой текущий лектор по Алгоритмам работает в промышленности и говорит, что A* часто используется на практике, особенно для GPS. Если вы используете евклидово расстояние в качестве эвристики, вы, как правило, получаете улучшения по сравнению с Диджстрой, игнорируя пути, которые бессмысленны в реальной жизни. Возможно, вы уже знаете, но Дейкстры можно описать как A* с эвристическим час(Икс)знак равно0 .
Jmite

Ответы:

8

Карты Google в 2009 году использовали иерархии сокращения - см. Этот технический доклад .

С тех пор были обнаружены некоторые потрясающие методы, способные выполнять маршрутизацию по пересеченной местности за доли миллисекунды - так называемые «оракулы расстояния между двумя метками». Смотрите здесь или ищите «Hub маркировка» или «Кратчайшие пути для масс». Я думаю, что слышал, что Бинг использует это. Он также имеет приложения, такие как возможность поиска ближайшей точки интереса (например, ближайшей заправочной станции) со сложностью, независимой от количества заправочных станций.

jkff
источник
2
Это, кажется, полезные ссылки. Тем не менее, вы можете: а) дать цитируемые ссылки и / или б) нарисовать общую картину того, как они работают? В частности, они решают проблему точно?
Рафаэль