Cómo Google Maps calcula rutas en todo el mundo: heurísticas diferenciales
Differential Heuristics
En 2007, Google Maps sorprendió al permitir arrastrar los puntos de inicio y fin de una ruta, recalculando el camino más corto al instante. Detrás de esa hazaña estaba una optimización de A* llamada heurísticas diferenciales. El autor de Red Blob Games, tras años de intentos fallidos por explicarla, decidió experimentar y aprender a fondo. Ahora publica una guía interactiva que visualiza con flechas y regiones cómo esta técnica reduce drásticamente el área explorada por A*, haciendo posible el cálculo rápido en mapas con millones de calles.
Aunque entendía el algoritmo, no lo entendía lo suficientemente bien como para enseñarlo.
- plomme
Muy buen artículo, como siempre, de Red Blob. Le dio la vuelta a mi suposición de alto nivel sobre el cálculo de rutas de Google Maps. Pensaba, recordando la clase de algoritmos, que Google Maps funcionaba tan rápido gracias a la "subestructura óptima" de la búsqueda del camino más corto. Es decir, que el camino más corto de A a C pasando por B también produce los caminos más cortos de A a B y de B a C, y que para la mayor parte de cualquier camino dado podrías enrutar a través de algunos caminos "intermedios" precalculados. Leer esto le da la vuelta en el sentido de que los puntos de referencia van detrás del destino, ¡y no en medio de la ruta! Muy útil.
- simonw
Discutido aquí hace cinco días: https://news.ycombinator.com/item?id=49079995
(La verdad, es un trabajo tan genial que merece una segunda conversación; esa solo llegó a 40 comentarios.)
- inigyou
Buen artículo y buenas demostraciones. Estaba un poco confundido con los colores: al menos una vez el texto habla de que las casillas azules son las que no necesitan ser revisadas gracias al punto de referencia, pero en realidad son verdes, y las azules son las que no se revisaban de todos modos. No soy daltónico.
Muchos de tus mapas consisten en habitaciones conectadas en unos pocos puntos. ¿Has considerado ejecutar primero la búsqueda de caminos a través del grafo de habitaciones y luego a través de cada habitación individualmente? Incluso podrías precalcular todos los caminos a través de una habitación de un portal a otro, pero probablemente no lo necesites, pero necesitarías precalcular cuán costosos son. Esto probablemente tenga un costo de búsqueda similar a poner un punto de referencia en cada habitación.