algorithm - way - tipos de busqueda heuristica

A*Algoritmo para gráficos muy grandes, ¿alguna idea sobre los atajos de almacenamiento en caché? (9)

Estoy escribiendo una simulación de mensajería / logística en los mapas de OpenStreetMap y me he dado cuenta de que el algoritmo A * básico como se muestra a continuación no será lo suficientemente rápido para mapas grandes (como el Gran Londres).

Los nodos verdes corresponden a los que se pusieron en la cola abierta de conjunto / prioridad y debido a la gran cantidad (todo el mapa es algo así como 1-2 millones), se tarda unos 5 segundos en encontrar la ruta representada. Lamentablemente, 100 ms por ruta es aproximadamente mi límite absoluto.

Actualmente, los nodos se almacenan tanto en una lista de adyacencia como en una matriz espacial de 100x100 2D.

Estoy buscando métodos en los que pueda intercambiar tiempo de preprocesamiento, espacio y, si es necesario, la optimización de la ruta, para consultas más rápidas. La fórmula de Haversine en línea recta para el costo heurístico es la función más costosa según el perfilador: he optimizado mi A * básico tanto como puedo.

Por ejemplo, estaba pensando que si elijo un nodo arbitrario X de cada cuadrante de la matriz 2D y ejecuto A * entre cada uno, puedo almacenar las rutas al disco para simulaciones posteriores. Al realizar consultas, puedo ejecutar la búsqueda A * solo en los cuadrantes, para llegar entre la ruta calculada previamente y la X.

¿Existe una versión más refinada de lo que he descrito anteriormente o quizás un método diferente que debería seguir? ¡Muchas gracias!

Para el registro, aquí hay algunos resultados de referencia para ponderar arbitrariamente el costo heurístico y calcular la ruta entre 10 pares de nodos seleccionados al azar:

Weight // AvgDist% // Time (ms) 1 1 1461.2 1.05 1 1327.2 1.1 1 900.7 1.2 1.019658848 196.4 1.3 1.027619169 53.6 1.4 1.044714394 33.6 1.5 1.063963413 25.5 1.6 1.071694171 24.1 1.7 1.084093229 24.3 1.8 1.092208509 22 1.9 1.109188175 22.5 2 1.122856792 18.2 2.2 1.131574742 16.9 2.4 1.139104895 15.4 2.6 1.140021962 16 2.8 1.14088128 15.5 3 1.156303676 16 4 1.20256964 13 5 1.19610861 12.9

Sorprendentemente, aumentar el coeficiente a 1.1 casi redujo a la mitad el tiempo de ejecución manteniendo la misma ruta.

Antigua pregunta, pero aún así:

Trate de usar diferentes montones que "montón binario". ''El mejor montón de complejidad asintótica'' es definitivamente el montón de Fibonacci y su página wiki tiene una buena descripción:

https://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times

Tenga en cuenta que el almacenamiento dinámico binario tiene un código más simple y está implementado sobre la matriz y el recorrido de la matriz es predecible, por lo que la CPU moderna ejecuta operaciones de almacenamiento dinámico binario mucho más rápido.

Sin embargo, dado el conjunto de datos lo suficientemente grande, otros montones ganarán sobre el montón binario, debido a sus complejidades ...

Esta pregunta parece un conjunto de datos lo suficientemente grande.

Creo que vale la pena resolver su idea con "cuadrantes". Más estrictamente, lo llamaría una búsqueda de ruta de baja resolución.

Puede elegir X nodos conectados que estén lo suficientemente cerca y tratarlos como un solo nodo de baja resolución. Divida todo su gráfico en tales grupos, y obtendrá un gráfico de baja resolución. Esta es una etapa de preparación.

Para calcular una ruta desde el origen hasta el destino, primero identifique los nodos de baja resolución a los que pertenecen y encuentre la ruta de baja resolución. Luego, mejore su resultado al encontrar la ruta en un gráfico de alta resolución, pero restringiendo el algoritmo solo a los nodos que pertenecen a los nodos de baja resolución de la ruta de baja resolución (opcionalmente, también puede considerar nodos vecinos de baja resolución hasta cierta profundidad )

Esto también puede generalizarse a múltiples resoluciones, no solo altas / bajas.

Al final, debe obtener una ruta lo suficientemente cerca como para ser óptima. Es localmente óptimo, pero puede ser algo peor que óptimo a nivel mundial en cierta medida, lo que depende del salto de resolución (es decir, la aproximación que hace cuando un grupo de nodos se define como un solo nodo).

Debería poder hacerlo mucho más rápido cambiando la optimización. Ver Admisibilidad y optimización en wikipedia.

La idea es usar un valor de epsilon que conduzca a una solución no peor que 1 + epsilon la ruta óptima, pero que hará que el algoritmo considere menos nodos. Tenga en cuenta que esto no significa que la solución devuelta siempre será 1 + epsilon veces la ruta óptima. Este es solo el peor de los casos. No sé exactamente cómo se comportaría en la práctica para su problema, pero creo que vale la pena explorarlo.

Se le dan varios algoritmos que se basan en esta idea en wikipedia. Creo que esta es su mejor apuesta para mejorar el algoritmo y que tiene el potencial de ejecutarse en su límite de tiempo y al mismo tiempo devolver buenos caminos.

Dado que su algoritmo maneja millones de nodos en 5 segundos, supongo que también usa montones binarios para la implementación, ¿correcto? Si los implementó manualmente, asegúrese de que se implementen como matrices simples y que sean montones binarios.

Existen algoritmos especializados para este problema que realizan muchos cálculos previos. Desde la memoria, el cálculo previo agrega información al gráfico que A * utiliza para producir una heurística mucho más precisa que la distancia en línea recta. Wikipedia da los nombres de varios métodos en http://en.wikipedia.org/wiki/Shortest_path_problem#Road_networks y dice que Hub Labeling es el líder. Una búsqueda rápida sobre esto aparece en http://research.microsoft.com/pubs/142356/HL-TR.pdf . Una más antigua, que usa A *, está en http://research.microsoft.com/pubs/64505/goldberg-sp-wea07.pdf .

¿Realmente necesitas usar Haversine? Para cubrir Londres, habría pensado que podría haber asumido una tierra plana y haber utilizado Pitágoras, o haber almacenado la longitud de cada enlace en el gráfico.

Hay docenas de variaciones A * que pueden ajustarse a la factura aquí. Sin embargo, debe pensar en sus casos de uso.

¿Estás limitado a la memoria (y también al caché)?
¿Puedes paralelizar la búsqueda?
¿La implementación de su algoritmo se usará solo en una ubicación (por ejemplo, Gran Londres y no en Nueva York o Mumbai o donde sea)?

No hay forma de que conozcamos todos los detalles que usted y su empleador conocen. Por lo tanto, su primera parada debería ser CiteSeer o Google Scholar: busque documentos que traten la búsqueda de rutas con el mismo conjunto general de restricciones que usted.

Luego, seleccione tres o cuatro algoritmos, realice la creación de prototipos, pruebe cómo se amplían y los afinan. Debe tener en cuenta que puede combinar varios algoritmos en la misma gran rutina de búsqueda de ruta basada en la distancia entre los puntos, el tiempo restante o cualquier otro factor.

Como ya se ha dicho, en base a la pequeña escala de su área objetivo, dejar caer Haversine es probablemente su primer paso para ahorrar un tiempo precioso en costosas evaluaciones de trigonometría. NOTA: No recomiendo usar la distancia euclidiana en coordenadas lat, lon: ¡vuelva a proyectar su mapa en, por ejemplo, un Mercator transversal cerca del centro y use coordenadas cartesianas en yardas o metros!

La precomputación es la segunda, y cambiar los compiladores puede ser una tercera idea obvia (cambie a C o C ++; consulte https://benchmarksgame.alioth.debian.org/ para obtener más detalles).

Los pasos adicionales de optimización pueden incluir deshacerse de la asignación dinámica de memoria y usar una indexación eficiente para la búsqueda entre los nodos (piense en el árbol R y sus derivados / alternativas).

Hay un gran artículo que Microsoft Research escribió sobre el tema:

http://research.microsoft.com/en-us/news/features/shortestpath-070709.aspx

El documento original está alojado aquí (PDF):

http://www.cc.gatech.edu/~thad/6601-gradAI-fall2012/02-search-Gutman04siam.pdf

Esencialmente, hay algunas cosas que puedes probar:

Comience tanto desde el origen como desde el destino. Esto ayuda a minimizar la cantidad de trabajo desperdiciado que realizaría al atravesar desde la fuente hacia el destino.
Use puntos de referencia y carreteras. Básicamente, encuentre algunas posiciones en cada mapa que sean caminos comúnmente tomados y realice algunos cálculos previos para determinar cómo navegar eficientemente entre esos puntos. Si puede encontrar un camino desde su fuente a un punto de referencia, luego a otros puntos de referencia, luego a su destino, puede encontrar rápidamente una ruta viable y optimizar desde allí.
Explore algoritmos como el algoritmo de "alcance". Esto ayuda a minimizar la cantidad de trabajo que hará al atravesar el gráfico al minimizar el número de vértices que deben considerarse para encontrar una ruta válida.

Por lo general, A * viene con demasiado consumo de memoria en lugar de problemas de tiempo.

Sin embargo, creo que podría ser útil calcular primero solo con nodos que son parte de "grandes calles". Por lo general, elegiría una autopista en lugar de un pequeño callejón.

Supongo que ya puede usar esto para su función de peso, pero puede ser más rápido si usa alguna Cola prioritaria para decidir qué nodo probar a continuación para viajar más.

También podría intentar reducir el gráfico a solo nodos que son parte de bordes de bajo costo y luego encontrar una forma de comenzar / finalizar al más cercano de estos nodos. Entonces tiene 2 caminos desde el principio hasta la "gran calle" y la "gran calle" hasta el final. Ahora puede calcular la mejor ruta entre los dos nodos que forman parte de las "grandes calles" en un gráfico reducido.

Trabajé en una importante empresa de navegación, por lo que puedo decir con confianza que 100 ms debería conseguirte una ruta desde Londres a Atenas incluso en un dispositivo integrado. Gran Londres sería un mapa de prueba para nosotros, ya que es convenientemente pequeño (cabe fácilmente en la RAM, esto no es realmente necesario)

En primer lugar, A * está completamente desactualizado. Su principal beneficio es que "técnicamente" no requiere preprocesamiento. En la práctica, debe preprocesar un mapa OSM de todos modos, por lo que es un beneficio inútil.

La técnica principal para darle un gran impulso de velocidad son las banderas de arco. Si divide el mapa en digamos secciones de 5x6, puede asignar una posición de 1 bit en un entero de 32 bits para cada sección. Ahora puede determinar para cada borde si alguna vez es útil cuando viaja a la sección {X,Y} desde otra sección. Muy a menudo, las carreteras son bidireccionales y esto significa que solo una de las dos direcciones es útil. Entonces, una de las dos direcciones tiene ese bit establecido, y la otra lo ha borrado. Puede que esto no parezca un beneficio real, pero significa que en muchas intersecciones se reduce la cantidad de opciones a considerar de 2 a solo 1, y esto requiere una operación de un solo bit.

GraphHopper hace dos cosas más para obtener un enrutamiento rápido, no heurístico y flexible (nota: soy el autor y puede probarlo en línea here )

Una optimización no tan obvia es evitar la asignación 1: 1 de nodos OSM a nodos internos. En cambio, GraphHopper usa solo uniones como nodos y guarda aproximadamente 1/8 de los nodos recorridos.
Tiene implementos eficientes para A *, Dijkstra o, por ejemplo, Dijkstra de uno a muchos. Lo que hace posible una ruta en menores de 1s a través de toda Alemania. La versión bidireccional (no heurística) de A * hace que esto sea aún más rápido.

Por lo tanto, debería ser posible obtener rutas rápidas para el gran Londres.

Además, el modo predeterminado es el modo de velocidad que hace que todo sea un orden de magnitudes más rápido (por ejemplo, 30 ms para rutas de ancho europeo) pero menos flexible, ya que requiere preprocesamiento ( Jerarquías de contracción ). Si no le gusta esto, simplemente desactívelo y ajuste aún más las calles incluidas para el automóvil o, probablemente, cree mejor un nuevo perfil para camiones, por ejemplo, excluya las calles y pistas de servicio que deberían darle un aumento adicional del 30%. Y como con cualquier algoritmo bidireccional, podría implementar fácilmente una búsqueda paralela.