Retroceder en una estrella

Paredes azules

Células resaltadas en verde = lista abierta

Celdas resaltadas en rojo = lista cerrada

enter image description here

Hola, ¿alguien puede decirme cómo puedo implementar el backtracking en un algoritmo de búsqueda de estrellas? Implementé la búsqueda de una estrella según wiki, pero no retrocede, lo que quiero decir con un retroceso es que la lista abierta (celdas verdes) contiene 2,0 y 3,3 como se muestra en la imagen, al llegar a 2, 0 el nodo actual “saltará” a 3,3 ya que el costo es ahora más de 3,3 y continúa la búsqueda desde allí, ¿cómo se puede hacer para que retroceda desde 2,0-> 2,1-> 2,2 … todo el camino de vuelta a 3,3 y comenzar la búsqueda desde allí?

tu imagen es como un mapa de cuadrícula 2d

Pero su texto sugiere un enfoque gráfico que es un poco confuso.

  • Para el mapa de cuadrícula 2D, los costos deben ser diferentes entre las celdas de la ruta

Tienes demasiado de cost=100 allí y, por lo tanto, no puedes retroceder en el camino. Debe boost o disminuir el costo en cada paso y completar solo las celdas que están cerca de las últimas celdas llenas. Esto se puede hacer por recursión en mapas grandes o escaneando el mapa completo o el recuadro delimitador para el último número rellenado en mapas pequeños.

  • Mire aquí para la implementación de C ++ A *

El retroceso

Se puede hacer escaneando los vecinos de las celdas de inicio / finalización después de que el relleno A * se mueva siempre al costo menor / mayor

ejemplo

En este ejemplo, empiece a llenar desde (2,0) hasta que (3,3) se golpee y luego retroceda desde (3,2) cost=8 hasta el menor costo (siempre cost-1 para el llenado incremental). Si necesita la ruta en orden inverso, empiece a llenar desde (3,3) lugar …

acelerar

A veces, el doble llenado acelera el proceso así que: Comience a llenar desde ambos extremos y deténgalo cuando se unan. Para reconocer qué celda está llena, desde ese punto puede usar valores positivos y negativos, o algunos rangos suficientemente grandes para los costos.

Puede seguir los signos de retroceso desde los dos nodos hasta que llegue al ancestro común (0,2), luego imprima los nodos que visitó cuando los sigue desde (2,0), seguidos de los nodos que visitó al seguir desde (3,3) , impreso en reversa

Para encontrar el ancestro común de dos nodos en un árbol de búsqueda A *, simplemente mantenga los dos “nodos actuales” y siga el dorso de lo que tenga el mayor costo g, hasta que los dos nodos actuales estén en el mismo lugar.

Vale mencionar que esto es algo raro de hacer, sin embargo. A * no es un recorrido basado en la stack, por lo que no retrocede.