“El algoritmo de ruta más corta” no sería una respuesta, ya que hay más de un algoritmo de ruta más corta. Los más conocidos son el algoritmo de Dijkstra y Bellman-Ford; estos no serían lo suficientemente rápidos por sí solos y usarían demasiada memoria para el enrutamiento en tiempo real en un GPS. El algoritmo heurístico A * sería más apropiado y se ha utilizado en algunos servidores de enrutamiento.
Una heurística importante para el enrutamiento en grandes redes de autopistas (y otros tipos de redes) es que una ruta desde un lugar pequeño a otro lugar lejano tiende a seguir caminos pequeños a caminos principales, luego permanece en los caminos principales hasta que nuevamente caminos hacia el destino. Muchos enrutadores usan esta observación: buscan desde ambos puntos finales (usando una variante de A * o el algoritmo de Dijkstra) favoreciendo las transiciones a carreteras más grandes, hasta que se encuentran en algún punto intermedio. Las jerarquías de contracción es un enfoque que procesa previamente la estructura de datos del mapa para hacer que este enfoque funcione de manera muy eficiente, y aunque es poco probable que Google divulgue sus algoritmos públicamente, es muy probable que Google Maps use jerarquías de contracción o algo estrechamente relacionado.
Como las jerarquías de contracción son un desarrollo bastante reciente, es más probable que el GPS de su automóvil use alguna variante de A *, probablemente con algún uso de la observación sobre rutas que van de pequeño a grande.
- ¿Existe un mejor patrón para aprender algoritmos de programación?
- Dada una cuadrícula N-por-M llena de números positivos, ¿cuál es el mejor programa para encontrar la ruta de arriba a la izquierda a la derecha que minimiza la suma de todos los números?
- Dados los pares 'n1' de corchetes "[]", los pares 'n2' de corchetes "{}" y los pares 'n3' de corchetes "()", ¿cómo podemos encontrar todas las combinaciones válidas posibles de todos estos pares de manera eficiente?
- ¿Cómo funciona el algoritmo de fijación de precios de Megabus?
- ¿Cómo deberíamos hacer un seguimiento de la mediana de una matriz en expansión?
