gps - una - ¿Cómo funciona el software de búsqueda de rutas?

que es un track en gps

Question

Pregunto a un nivel bastante alto, independiente del lenguaje.

¿Cómo funciona la búsqueda de rutas (como se encuentra en Google Maps ''Obtener direcciones'' o un GPS)? No puedo creer que intente todas las rutas concebibles y elija el más corto / más rápido, etc. Debe haber alguna forma lógica de encontrar la mejor ruta, dado un punto de inicio y un punto final.

Cualquier tipo de explicación sería genial.

Answer 1

Deberías leer sobre el problema de la ruta más corta y el algoritmo de Dijkstra . Ambos se usan para determinar el camino a tomar entre dos puntos. Google Maps (y otras aplicaciones de mapeo) agregan características adicionales (como reencaminamiento, etc.), pero estos dos conceptos son la premisa básica de cómo se resuelve el problema.

Answer 2

Una publicación muy antigua, pero busqué esta pregunta en particular y encontré un buen artículo con la explicación: http://blog.kdgregory.com/2011/12/how-gps-calculates-routes.html

Básicamente, utiliza un algoritmo de búsqueda A * y una clasificación de ruta (ruta corta, ruta larga, etc.) para reducir los requisitos de computación y memoria.