Algoritmo de Dijkstra en grandes gráficos

15

Estoy muy familiarizado con Dijkstra y tengo una pregunta específica sobre el algoritmo. Si tengo un gráfico enorme, por ejemplo 3.500 millones de nodos (todos los datos de OpenStreetMap), entonces claramente no podría tener el gráfico en la memoria, por lo que el gráfico se almacena en el disco en una base de datos.

Hay bibliotecas disponibles para calcular las rutas más cortas en tales gráficos. ¿Cómo lo hacen? Más específicamente, ¿cómo cargan la parte requerida del gráfico para ejecutar el algoritmo de Dijkstra?

Obtener la lista de adyacencia de cada vértice visitado requeriría aproximadamente 1,500 consultas de la base de datos por 10,000 nodos de acuerdo con mis datos estadísticos, por lo que claramente no es así como lo hacen. Eso sería demasiado lento.

¿Cómo lo hicieron? Estoy tratando de implementarlo yo mismo.

dimitris93
fuente
2
¿Estás seguro de que usan Dijkstra? Hay muchos otros algoritmos de ruta más corta que pueden adaptarse mejor a la situación que usted describe.
David Richerby
1
¿Has mirado el código? ¿Cómo deberíamos saberlo? "consultas de bases de datos": ¿espero que no use un DBMS para almacenar gráficos?
Raphael
@DavidRicherby sí, estoy seguro, mira este enlace
dimitris93
2
"[I] t sería un proceso extremadamente tedioso examinar el código C puro". Pero esa es la única forma de saber qué hace el código. Así que usted está pidiendo que haga su tarea tediosa para usted, que no es el mejor anuncio para su pregunta ...
David Richerby
1
@ Shiro Usted pregunta explícitamente: "¿Cómo hacen esto?" Si esa no es realmente la pregunta que desea hacer, debe reformularla.
Raphael

Respuestas:

6

Hay bibliotecas disponibles para calcular las rutas más cortas en tales gráficos. ¿Cómo lo hacen? Más específicamente, ¿cómo cargan la parte requerida del gráfico para ejecutar el algoritmo de Dijkstra?

Puede usar una base de datos, un formato de archivo personalizado para leer desde el disco y una configuración en memoria.

Pero, según mi experiencia, el uso de una base de datos es aproximadamente de 5 a 10 veces más lento y requiere mucha más memoria que escribir su propio formato de archivo basado en un formato de lista enlazada 'simple'.

Lo bueno es que hay varios marcos de software que utilizan OSM que son de código abierto para que pueda ver directamente el código, por ejemplo, consulte aquí . En el motor de enrutamiento de código abierto GraphHopper , es muy fácil cambiar de una configuración de asignación de memoria (basada en disco) a la configuración en memoria, ambas utilizando el mismo formato. La configuración "mmap" incluso permite el uso en dispositivos móviles con memoria restringida y este último funciona mucho más rápido si tiene la RAM necesaria, por ejemplo, en un servidor. Por ejemplo, para un gráfico mundial (> 100 millones de nodos), entonces necesita alrededor de 8-10 gb de RAM, además de mucha más RAM si desea acelerar todo aún más, por ejemplo, con Jerarquías de Contracción: aproximadamente 5-8 gb más para cada vehículo que desee.

El formato es muy simple y básicamente almacena solo los datos que necesita con algunos trucos para hacerlo compacto. Lea más sobre esto aquí . Descargo de responsabilidad: soy el autor de GraphHopper.

En cuanto a las otras respuestas:

El algoritmo de Dijkstras, aunque aplicable, se considera no óptimo para este problema.

El Dijkstra 'normal' puede tener un rendimiento muy razonable (<1s para consultas en todo el país como su ejemplo de 3 millones de nodos) y es óptimo en el 'sentido de la teoría', pero necesita un poco de ajuste para ser rápido en los escenarios de producción. Y técnicas como las Hieraquias de Contracción usan una modificación bidireccional de la misma y funcionan muy bien.

Las redes de carreteras son jerárquicas y planas.

Las redes de carreteras son jerárquicas solo para automóviles y no planas (puentes, túneles, ...)

Karussell
fuente
Tengo una pregunta más. ¿Cómo encuentra el NodeIDnodo más cercano al latitude/longitude? Eso es necesario para calcular la ruta más corta A-> B. Y también debemos tener en cuenta que A y B podrían no existir como nodos, porque no todos los metros cuadrados contienen un nodo. Por lo tanto, debemos encontrar los 2 NodeID más cercanos de A y B.
dimitris93
Eso se hace en LocationIndexTree, que es una especie de árbol cuádruple que almacena de manera eficiente los NodeID en una celda que tiene, por ejemplo, para GraphHopper un radio de ~ 500 m. Si no se encuentra nada, expande el radio hasta cierto grado. Esto suena simple en teoría, pero es muy complejo ya que puede tener bordes que cruzan el área, debe ser eficiente al crearlo, consultarlo y mucho más.
Karussell
¿No son los árboles KD más eficientes cuando se busca al vecino más cercano? ¿Por qué elegiste QuadTrees sobre KD-Trees? Estoy implementando KD-Trees para mi motor de enrutamiento en este momento. Comencé a implementar QuadTrees pero paré porque pensé que KD-Trees es lo mismo, pero más fácil de codificar y más rápido para consultar al vecino más cercano. Me equivoco ?
dimitris93
Cuando utilizo quadtrees no hay necesidad de almacenar explícitamente el cuadro delimitador, lo que le da una ventaja de almacenamiento, lo que fue más crítico para mi caso de uso (también encuentro los quadtrees más fáciles). La velocidad de consulta no es un problema. De hecho, alguien estudió tales intentos y superó cualquier otra implementación, incluido. KD árboles, pero supongo que todo depende de la implementación específica ...
Karussell
Si mira la página 9 de este pdf de Stanford, buscar el vecino más cercano en KD-Trees no requiere que conozca los cuadros delimitadores. Y otra cosa es que, dado que conocemos todos los puntos de antemano, podemos crear un árbol equilibrado de altura logn. ¿Todavía estás seguro de que los quadtrees tienen alguna ventaja sobre los árboles kd?
dimitris93
2

No necesita colocar todos los bordes adyacentes en la cola de prioridad. "Mentir" al algoritmo de Dijkstra y darle solo el vértice más corto, v, incidente al vértice, digamos w, sacado de la pila. Luego, cuando v es sacado de la cola, dices "¡Uy!" Cometí un error y también debería haberte dado este vértice, que es el siguiente más cercano al vértice w. Se ve fácilmente que de esta manera tendrá una solución correcta y el tamaño de la cola se reduce drásticamente a un vértice incidente solo en lugar de los muchos. Sin embargo, debe realizar un seguimiento de las incidencias para proporcionar siempre el siguiente vértice más cercano, cuando sea necesario. Uno de los comentarios afirmó que las redes de carreteras son planas que son incorrectas. De hecho, un estudio ha demostrado que son altamente no planas. Piense en todas las autopistas que cruzan a través de puentes a través de una ciudad que inducen muchas no planaridades.

user49040
fuente
0

El algoritmo de Dijkstras, aunque aplicable, se considera no óptimo para este problema, aunque las variantes más eficientes podrían considerarse "similares". Hay varias simplificaciones. Las redes de carreteras son jerárquicas y planas . Aquí están los enfoques básicos. el área se conoce generalmente como "planificación de rutas en redes de carreteras".

  • Se puede "compilar" una estructura gráfica a partir de los datos de la lista de adyacencia. Este es el enfoque en la biblioteca que cita , SpatiaLite. estas estructuras de gráficos se almacenan en un formato binario comprimido donde las ubicaciones de los gráficos están representadas por enteros codificados en binarios, etc., por lo que la representación gráfica y la manipulación ocupan mucho menos espacio que almacenar todos los nombres de carreteras, etc .; parece que el algoritmo SpatiaLite no está "en línea" y se ejecuta completamente en la memoria.

  • Hay algoritmos paralelos / distribuidos. ver, por ejemplo, Gráfica GPU escalable transversal / Merrill, Garland, Grimshaw.

  • la pregunta usa terminología cliente-servidor, es decir, "consultas". los algoritmos no se ejecutan al "consultar" la base de datos en el sentido cliente-servidor. los lenguajes de consulta de nivel superior, como SQL, son una interfaz para la base de datos y pueden usarse para transmitir la solicitud para calcular las rutas mínimas, pero el algoritmo no los usa internamente. generalmente el algoritmo se ejecuta "dentro de la base de datos", es decir, completamente "del lado del servidor". por lo tanto, escribir un algoritmo de ruta más corta en las consultas de la base de datos es factible para redes pequeñas pero no para medianas / grandes

  • Hay otro enfoque donde las estimaciones dentro de porcentajes pequeños pueden ser aceptables. La idea básica es mantener un índice de distancias entre nodos. ver, por ejemplo, Estimación rápida y precisa de las rutas más cortas en gráficos grandes / Gubichev, Bedathur, Seufert, Weikum

  • Esta tesis doctoral (¡235p!) es especialmente aplicable. Planificación de rutas en redes de carreteras / Schultes

  • Algunos algoritmos utilizan muchas de estas ideas y otros, están altamente afinados y patentados y están al borde de los secretos comerciales competitivos. por ejemplo, de Google. Puede haber algunos medios engañosos sobre este tema. por ejemplo , el algoritmo simple y elegante que hace posible Google Maps que afirma / implica que Google usa el algoritmo Dijkstras sin ninguna cita.

vzn
fuente
1
Google Maps ciertamente se ha actualizado a algo mejor que Dijskstra. Todos los desarrolladores competentes a mitad de camino usarían A * para mapas de carreteras, pero en mi trabajo anterior descubrimos que el motor de Google podía volver a planificar rutas de 2500 km a través de un punto de referencia en <100 ms. Eso es demasiado rápido para A *, por lo que es probable que usen algo como ArcFlags.
MSalters
La respuesta de Karussell desafía esta frase inicial "El algoritmo de Dijkstras, aunque aplicable, se considera no óptimo para este problema", que no esperaba que fuera controvertido. Existe un gran apoyo para la afirmación en la tesis de Schultes (al principio), que también es una encuesta muy completa / reciente del área, y también explica las "aproximaciones" jerárquicas y planas. Desafortunadamente, no parece haber indicios de los algoritmos reales de Google en la literatura abierta sobre búsqueda rápida.
vzn
-2

En conjuntos de datos extremadamente grandes como ese, para obtener resultados tan rápidos, me parece mejor usar una estructura de datos de búsqueda de unión con compresión de ruta. Sin embargo, si está buscando usar solo el algoritmo de Djikstra y optimizarlo, todo se reduce a la información que tiene cada nodo en el gráfico. Lo más probable es que no necesite hacer las 1.500 consultas.

Por ejemplo, considere el siguiente ejemplo. Digamos que estoy tratando de encontrar los grados de separación entre 2 actores (el número de Bacon) y quiero encontrar la ruta menos ponderada (ruta usando las películas más nuevas posibles). Ahora, digamos que tengo una función llamada shortestPath(actor A, actor B);. Considere el siguiente escenario.

Si el actor A ha estado actuando desde 1970 y el actor B ha estado actuando desde 2000, dada esa información, sería mucho más lógico encontrar un camino que comience desde la primera película del actor B y luego atraviese su camino hacia el actor A. Como en lugar de repetir cada película en la que ha actuado el actor A.

Por lo tanto, el punto principal es que la optimización del algoritmo de Djikstra realmente depende de cuál sea su conjunto de datos. Debería proporcionar más información sobre lo que implica su conjunto de datos para ayudarlo a optimizar su algoritmo.

EDITAR: Digamos que está tratando de encontrar el camino más corto entre 2 ciudades en el mismo país y si este país es más largo que ancho, por ejemplo, Argentina, puede hacer sus consultas en función de la longitud y la latitud de los países. fronteras Luego puede comenzar a recorrer verticalmente (usando la longitud) en lugar de horizontalmente. Ofc, tendría que haber un manejo de excepciones, pero se entiende la idea general.

Jonathan
fuente
1
¿Cómo se usa Union-Find en Dijkstra?
Raphael
Los datos son datos espaciales, latitud y longitud. Pensé que eso estaba claro.
dimitris93