¿Cuáles son algunas optimizaciones comunes que los clientes de GPS como Google Maps usan además de los algoritmos elementales de ruta más corta como la búsqueda A *?

No estoy seguro de lo que quiere decir con “clientes de GPS”, pero supongo que se refiere a encontrar rutas más cortas (o mejores) en un mapa de carreteras. Una optimización fundamental es reconocer que la mejor ruta desde un lugar pequeño X a un lugar pequeño Y es casi siempre desde X hacia caminos más grandes, luego a través de los caminos más grandes, luego hacia los caminos pequeños que conducen a Y. Entonces, en lugar de una A * búsqueda de X a Y, hacemos búsquedas bidireccionales de X y de Y, cada una restringida a aumentar solo el tamaño de la carretera. Puede trabajar con una clasificación predefinida de “tamaños” de carreteras, pero los algoritmos actuales más rápidos preprocesan los datos del mapa para encontrar una buena jerarquía. Las jerarquías de contracción (Jerarquías de contracción: enrutamiento jerárquico más rápido y simple en redes de carreteras) son un buen ejemplo de esto.