Alternativas más rápidas al algoritmo de Dijkstra para el sistema de GPS

Question

Soy un verdadero fanático de la velocidad si se trata de algoritmos y de los complementos que hice para un juego.

La velocidad es ... un poco ... no es satisfactoria. Especialmente mientras manejas con un automóvil y no sigues tu camino, el camino tiene que ser recalculado ... y lleva un tiempo, así que el GPS del juego está acumulando muchas señales de "sentido incorrecto" (y acumulando las señales significa más cálculos después, para cada movimiento equivocado) porque quiero un sistema rápido y en vivo, que se actualiza constantemente.

he cambiado el algoritmo antiguo (algunos simples aplicación Dijkstra) para impulsar :: de Dijkstra para calcular una ruta desde el nodo A al nodo B

(lista de nodos total es de alrededor de ~ nodos 15k con ~ conexiones de 40k, por curiosidad la gente aquí es el mapa: http://gz.pxf24.pl/downloads/prv2.jpg (12 MB), los bordes en las líneas rojas son los nodos),

pero en realidad no aumentó en velocidad. (Al menos no notablemente, tal vez 50 ms).

La información que se almacena en la matriz de nodos es:

The ID of the Node, 
The position of the node, 
All the connections to the node (and which way it is connected to the other nodes, TO, FROM, or BOTH) 
Distance to the connected nodes. 

Tengo curiosidad por si alguien sabe algunas alternativas más rápidas en C/C++? ¿Alguna sugerencia (+ ejemplos de código?) Son apreciadas.

---

Si alguien está interesado en el proyecto, aquí está (fuente + binarios):

https://gpb.googlecode.com/files/RouteConnector_177.zip

En este video se puede ver lo que el sistema GPS es como:

http://www.youtu.be/xsIhArstyU8

Como puede ver, la ruta roja se está actualizando lentamente (bueno, para nosotros, los jugadores, es lenta).

(Bytheway: los espacios entre las líneas rojas se han solucionado hace mucho tiempo: p)

Answer 1

Dado que este es un GPS, debe tener un destino fijo. En lugar de calcular la ruta desde su nodo actual hasta el destino cada vez que cambia el nodo actual, puede encontrar las rutas más cortas desde su destino a todos los nodos: simplemente ejecute Dijkstra una vez que comience desde el destino. Esto llevará tanto tiempo como una actualización tome en este momento.

Luego, en cada nodo, guarde prev = the node previous to this on the shortest path to this node (desde su destino). Actualiza esto a medida que calcula las rutas más cortas. O puede usar una matriz prev[] fuera de los nodos; básicamente, cualquier método que esté utilizando para reconstruir la ruta ahora debería funcionar.

Al mover su automóvil, su ruta está dada por currentNode.prev -> currentNode.prev.prev -> ....

Esto resolverá el retraso de actualización y mantendrá su camino óptimo, pero aún tendrá un pequeño retraso al ingresar a su destino.

Debe considerar este enfoque incluso si planea usar A * u otras heurísticas que no siempre dan la respuesta óptima, al menos si todavía tiene retraso con esos enfoques.

Por ejemplo, si usted tiene este gráfico:

1 - 2 cost 3 
1 - 3 cost 4 
2 - 4 cost 1 
3 - 4 cost 2 
3 - 5 cost 5 

La matriz prev se vería así (calculada cuando se calcule la distancia d[]):

 1 2 3 4 5 
prev = 1 1 1 2 3 

Significado:

shortest path FROM TO 
       1 2 = prev[2], 2 = 1, 3 
       1 3 = prev[3], 3 = 1, 3 
       1 4 = prev[ prev[4] ], prev[4], 4 = 1, 2, 4 (fill in right to left) 
       1 5 = prev[ prev[5] ], prev[5], 5 = 1, 3, 5 
       etc. 

Answer 2

Para hacer que el inicio sea instantáneo, puede hacer trampa en la siguiente w sí.

Tienen un conjunto bastante pequeño de "nodos de la carretera principal". Para cada nodo define su "vecindad" (todos los nodos dentro de una cierta distancia). Almacene las rutas más cortas desde cada nodo de la carretera principal a cada uno. Almacene las rutas más cortas hacia/desde cada nodo hasta sus principales vías públicas.

Si los dos nodos están en el mismo vecindario, puede calcular la mejor respuesta sobre la marcha. De lo contrario, considere solo las rutas de la forma, "aquí al nodo principal de la vía pública cerca de mí a la vía pública más importante cerca de él". Dado que ya precalculó esos y tiene un número limitado de combinaciones, debe calcular rápidamente una ruta sobre la marcha.

Luego, el desafío se convierte en elegir un conjunto de nodos de vías principales. Debería ser un conjunto bastante pequeño de nodos por el que deberían pasar la mayoría de las rutas, así que elija un nodo cada cierto tiempo en las calles principales. Una lista de un par de cientos debería ser más que suficiente para su mapa.