¿Se utiliza el algoritmo Dijkstras en los sistemas modernos de búsqueda de rutas?

10

¿Se utiliza el algoritmo de Dijkstra en los sistemas modernos de búsqueda de rutas, como los mapas de Google o el satélite en su automóvil? Si no, entonces ¿qué es?

algorithms graphs shortest-path applied-theory chopper draw lion4
fuente
Supongo que te refieres al componente de enrutamiento que encuentra tu camino, una vez que el GPS, que es principalmente un Syatem de posicionamiento global, ha determinado dónde estás . Otro caso más de una cola que menea a un perro.
babou
1
No puedo dar una fuente para esto, pero mi profesor actual de Algoritmos trabaja en la industria y dice que se usa mucho en la práctica, especialmente para GPS. Si usa la Distancia Euclidiana como una heurística, tiende a obtener mejoras sobre Dijstra ignorando los caminos que no tienen sentido en la vida real. Puede que ya lo sepas, pero Dijkstra se puede describir como A ∗ con heurística h ( x ) = 0 . A∗A∗h(x)=0
jmite

Respuestas:

8

Google Maps en 2009 utilizados contracción Jerarquías - ver esta charla técnica .

Desde entonces, se han descubierto algunos métodos alucinantes, capaces de realizar rutas a campo traviesa en milisegundos fraccionados, los llamados "oráculos de distancia de etiquetado de dos saltos". Consulte aquí o busque "Etiquetado de concentradores" o "Rutas más cortas para las masas". Creo que escuché que Bing usa este. También tiene aplicaciones como la capacidad de encontrar el punto de interés más cercano (por ejemplo, la estación de servicio más cercana) con una complejidad independiente de la cantidad de estaciones de servicio.

jkff
fuente
2
Esto parece ser referencias útiles. Sin embargo, ¿puede a) dar referencias citables y / ob) pintar el panorama general de cómo funcionan? En particular, ¿resuelven el problema exactamente?
Raphael