Hay trabajos como Reach for A * de investigadores de Microsoft y Highway Hierarchies de Sanders y Schtolz (si deletreo el nombre correctamente) de Karlsruhe Uni . Ambos reducen mucho el orden de los cálculos y se aceleran mil veces en gráficos grandes (vea los resultados en los documentos vinculados). El último trabajo condujo a la Máquina de enrutamiento de código abierto , que desafortunadamente no es lo suficientemente popular y no está adaptada (no pude compilarlo aunque lo intenté mucho).
Al mismo tiempo, los dbs que probé, Spatialite y PgRouting, según sus documentos, ofrecen solo algoritmos Dijkstra y A * . Ni siquiera he mencionado la búsqueda bidireccional mencionada, lo que ahorra tiempo de cálculo dos veces en mi experiencia.
¿Hay mejores algoritmos para bases de datos u otras aplicaciones?
fuente
Respuestas:
La verdad es que la mayoría de las personas usa una variación personalizada del algoritmo A * . Verá esto en la mayoría de los "grandes" (no puedo decir quiénes son en un foro público, pero puedo decirle que probablemente use uno de ellos, garantizado), donde la modificación de la heurística es muy dependiente de los conjuntos de datos que usan.
Ya mencionaste pgrouting , lo que yo consideraría una opción "tradicional". Es bueno para hacer algoritmos de enrutamiento simples y para la mayoría de los problemas. También es fácil de usar y utiliza una base de datos tradicional en su backend.
Sin embargo, realmente depende de la escala y el tipo de problema que está tratando de resolver y el enrutamiento es un problema gráfico .
Una vez más, los "grandes" generalmente tienen una gran cantidad de datos asociados con su gráfico (por ejemplo, datos de tráfico, rutas de autobuses, rutas de senderismo) que afectan el algoritmo de enrutamiento. Estos se conocen como planificadores de viajes multimodales (donde también tiene la opción de planificar "modos", sin carriles bici, solo transporte público, ese tipo de cosas). Puede pensar cómo la planificación del viaje también se convierte en un asunto sensible al tiempo (es decir, si se camina hacia atrás unos bordes hacia atrás, usted será capaz de coger el metro que le lleva a su destino hacia adelante mucho más rápido que si usted acaba de intentar navegar por los bordes hacia adelante usando el costo más bajo).
Los "grandes" no almacenan sus datos en una base de datos tradicional per se, usan gráficos precalculados (¡bienvenidos clusters de hadoop / mapreduce!). Como puede imaginar, estos gráficos se vuelven realmente grandes, por lo que saber cómo conectar los bordes de los gráficos adyacentes puede ser un desafío.
De todos modos, le recomendaría que mire algunos proyectos de gráficos de enrutamiento multimodales:
Graphserver viene a la mente. No hay mucha documentación, sino mucha genialidad de codificación pura (AFAIK, creo que MapQuest utiliza una variación de este proyecto para algunos de sus productos de enrutamiento).
Otra opción sería OpenTripPlanner, que tiene muchas personas inteligentes detrás (incluidas personas de Graphserver).
fuente
No estoy seguro si es más nuevo pero pgRouting tiene un algoritmo Shooting-Star :
La extensión de Network Analyst de ESRI utiliza el enfoque jerárquico que mencionó para limitar los tiempos de resolución:
Hay una muy detallada de papel blanco con ejemplos de este enfoque en el sitio de ESRI - sin embargo, requiere que iniciar sesión para descargar (Rutas jerárquicos en ArcGIS Network Analyst Libro Blanco).
fuente
La Jerarquía de Contracción es un algoritmo muy rápido:
Este algoritmo es compatible con RAM mientras se ejecuta una consulta (para mantener un gráfico contratado se necesita más RAM, así como un preprocesamiento masivo)
Existen algunos otros algoritmos, incluidos los que resuelven el enrutamiento de transporte público:
Microsoft también está investigando un poco:
(bueno, Daniel Delling también es de Karlsruhe)
Puede obtener una buena introducción y una descripción general de los algoritmos disponibles:
Advertencia: conferencias alemanas (!). ¡pero al menos los encabezados pueden ayudarlo a obtener más información (ALT, Arc-Flags, CHASE, ...) o la literatura adjunta!
actualizar
GraphHopper ahora implementa jerarquías de contracción y también otros algoritmos, también puede probar la demostración .
fuente