¿Cómo encontrar el camino más corto con los nodos de agujero de gusano?

Este es un ejemplo de lo que quiero hacer a través del código. Sé que puede usar la búsqueda de puntos de salto para pasar fácilmente del nodo verde al nodo rojo sin problemas, o incluso A *. Pero, ¿cómo se calcula esto con urdimbres?

En la imagen, puede ver que solo se necesitan 8 movimientos para pasar del nodo verde al nodo rojo al tomar el camino azul. El camino azul mueve instantáneamente su posición de un nodo morado al siguiente. El espacio en el medio que cuesta 2 movimientos es un punto entre dos zonas de urdimbre al que debes moverte para llegar.

Es claramente más rápido tomar el camino azul, ya que solo necesita moverse la mitad (aproximadamente) hasta el camino amarillo, pero ¿cómo hago esto programáticamente?

Con el fin de resolver este problema, supongamos que hay varias "deformaciones" púrpuras alrededor del gráfico que puede utilizar, Y sabemos exactamente dónde se deformará cada punto púrpura y dónde están en el gráfico.

Algunas urdimbres púrpuras son bidireccionales, y otras no lo son, lo que significa que a veces solo puede ingresar una urdimbre desde un lado, pero no retroceder después de la deformación.

Pensé en la solución, y solo concluí que sería capaz de calcular el problema al verificar la distancia a cada punto de deformación (menos los puntos unidireccionales), y la diferencia entre esos puntos y los puntos cercanos a ellos .

El programa tendría que descubrir de alguna manera que es más beneficioso tomar la segunda deformación, en lugar de caminar desde el primer salto. Entonces, en lugar de mover 6 puntos, luego deformar, luego mover los 8 pasos restantes a pie (que también es más rápido que no usar deformaciones), tomaría los 6 movimientos, luego los dos movimientos a la segunda deformación.

EDITAR: Me di cuenta de que el camino azul en realidad tomará 12 movimientos, en lugar de 8, pero la pregunta sigue siendo la misma.

La mayoría de los algoritmos de búsqueda de ruta se definen en términos de gráficos, no en términos de cuadrículas. En un gráfico, una conexión entre dos nodos distantes no es realmente un problema.

Sin embargo, debe tener cuidado con sus heurísticas. Con agujeros de gusano, la distancia mínima entre dos nodos ya no es la distancia euclidiana y la distancia no satisface la desigualdad del triángulo. Tales heurísticas son inadmisibles para A *. Por lo tanto, no puede usar A * fácilmente.

Por supuesto, los algoritmos de búsqueda de rutas como Dijkstra que no utilizan una heurística seguirán funcionando. Esto es más como una búsqueda de amplitud y seleccionará sus agujeros de gusano sin esfuerzo adicional. Sin embargo, Dijkstra visitará más nodos que A * con una buena heurística. (Dijkstra es equivalente a A * con heuristic(x) = 0.)

Creo que A * funcionará si usas una heurística que trata todos los agujeros de gusano salientes como un agujero de gusano directamente al objetivo: la heurística puede subestimar la distancia, pero nunca debe sobreestimarla. Es decir, la heurística sería:

def wormhole_heuristic(x):
  return min(euclidean_distance(x, g) for g in [goal, wormholes...])

Para una heurística muy precisa, puede (recursivamente) agregar la distancia desde el punto final del agujero de gusano hasta la meta o el siguiente agujero de gusano. Es decir, como cálculo previo, podría realizar una búsqueda de ruta en el subgrafo (totalmente conectado) que contiene todos los agujeros de gusano y el objetivo, donde la distancia entre dos nodos es su distancia euclidiana. Esto puede ser beneficioso si el número de agujeros de gusano es mucho menor que el número de células accesibles en su cuadrícula. La nueva heurística sería:

def wormhole_heuristic(x):
  direct = euclidean_distance(x, goal)
  via_wormhole = min(euclidean_distance(x, w) + wormhole_path_distance(w, goal) for w in wormholes)
  return min(direct, via_wormhole)

Como @Caleth señala en los comentarios, todo esto es muy sintonizable y podemos mejorar la primera heurística del agujero de gusano sin hacer un recorrido completo a través de la red de agujeros de gusano, agregando la distancia entre la última salida del agujero de gusano y el objetivo. Debido a que no sabemos qué salida de agujero de gusano se usará en último lugar y no debemos sobrestimarla, tenemos que asumir la salida más cercana a la meta:

def wormhole_heuristic(x):
  direct = euclidean_distance(x, goal)
  to_next_wormhole = min(euclidean_distance(x, w) for w in wormholes)
  from_last_wormhole = min(euclidean_distance(w.exit, goal) for w in wormholes)
  via_wormhole = to_next_wormhole + from_last_wormhole
  return min(direct, via_wormhole)

Tienes un gráfico con 6 vértices en una cuadrícula con coordenadas:

A ( 0,0)
B ( 4,7)
C ( 7,4)
D (10,4)
E (16,2)
F (16,0)

Puede generar un gráfico completo en esos vértices y asignar un costo a cada borde donde el costo es MAX( ABS( x1 - x2 ), ABS( y1 - y2 ) )para bordes estándar y un costo de 0 para agujeros de gusano.

Esto le dará los costos (como una matriz de adyacencia):

   A  B  C  D  E  F
- -- -- -- -- -- --
A  -  7  7 10 16 16
B  7  -  0  6 12 12
C  7  0  -  3  9  9
D 10  6  3  -  0  6
E 16 12  9  0  -  2
F 16 12  9  6  2  -

Si hay deformaciones unidireccionales, solo cree bordes en el gráfico (o matriz de adyacencia) que vayan en esa dirección pero no en el opuesto.

Luego puede usar el algoritmo de Dijkstra con una cola de prioridad .

Comience desde Ay empuje cada borde adyacente hacia la cola de prioridad:

Formato: (ruta: costo)

queue     = [ (A-B : 7), (A-C : 7), (A-D : 10), (A-E : 16), (A-F : 16) ]

A medida que los artículos se colocan en la cola, realice un seguimiento del costo mínimo para cada vértice y solo empuje las rutas hacia la cola si es un costo menor que el costo mínimo existente.

min-costs = { A: 0, B: 7, C: 7, D: 10, E: 16, F: 16 }

Elimine el primer elemento de la cola y, si su costo aún coincide con el costo mínimo, empuje todas las rutas compuestas formadas por esa ruta y sus bordes adyacentes nuevamente a la cola prioritaria (si las rutas compuestas tienen un costo menor que el mínimo existente):

Retirar: (A-B : 7)

• Probar (A-B-A : 14)- rechazar como mayor costo
• Probar (A-B-C : 7)- rechazar con el mismo costo
• Probar (A-B-D : 13)- rechazar como mayor costo
• Probar (A-B-E : 19)- rechazar como mayor costo
• Probar (A-B-F : 19)- rechazar como mayor costo

retirar (A-C : 7)

• Probar (A-C-A : 14)- rechazar como mayor costo
• Probar (A-C-B : 7)- rechazar con el mismo costo
• Probar (A-C-D : 10)- rechazar con el mismo costo
• Probar (A-C-E : 16)- rechazar con el mismo costo
• Probar (A-C-F : 16)- rechazar con el mismo costo

retirar (A-D : 10)

• Probar (A-D-A : 20)- rechazar como mayor costo
• Probar (A-D-B : 16)- rechazar como mayor costo
• Probar (A-D-C : 13)- rechazar como mayor costo
• Probar (A-D-E : 10): insertar en la cola
• Probar (A-D-F : 16)- rechazar con el mismo costo

Ahora la cola se verá así:

queue     = [ (A-D-E : 10), (A-E : 16), (A-F : 16) ]
min-costs = { A: 0, B: 7, C: 7, D: 10, E: 10, F: 16 }

retirar (A-D-E : 10)

• Probar (A-D-E-A : 26)- rechazar como mayor costo
• Probar (A-D-E-B : 22)- rechazar como mayor costo
• Probar (A-D-E-C : 19)- rechazar como mayor costo
• Probar (A-D-E-D : 10)- rechazar con el mismo costo
• Probar (A-D-E-F : 12): insertar en la cola

Entonces la cola es:

queue     = [ (A-D-E-F : 12), (A-E : 16), (A-F : 16) ]
min-costs = { A: 0, B: 7, C: 7, D: 10, E: 10, F: 12 }

Elimine (A-D-E-F : 12), descubra que ha llegado al nodo de destino con un costo de 12.

Nota: los caminos (A-B-C-D-E-F), (A-C-D-E-F)y (A-D-E-F)todos tienen el mismo costo mínimo de 12.

Configure una matriz que contenga todos los vértices y use el algoritmo de Floyd-Wallenstein-Algoritmo o el algoritmo de Bellman-Ford. Ambos darán como resultado una matriz con los caminos más cortos posibles entre todos los puntos. Luego puede recorrer la matriz para encontrar el camino más corto que conecta dos puntos. (su problema es el mismo que un TSP asimétrico).