algorithm - Retroceder en una estrella

search a-star

Question

Paredes azules

Celdas resaltadas en verde = lista abierta

Celdas resaltadas en rojo = lista cerrada

Hola, ¿alguien puede decirme cómo puedo implementar el retroceso en un algoritmo de búsqueda en estrella? He implementado la búsqueda de una estrella de acuerdo con wiki, pero no retrocede, lo que quiero decir con 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" a 3,3 ya que el costo ahora es más de 3,3 y continuará la búsqueda desde allí, ¿cómo se puede hacer para retroceder desde 2,0-> 2,1-> 2,2 ... todo el camino de regreso a 3,3 y comenzar la búsqueda desde allí?

Answer 1

Puede seguir los backpointers de los dos nodos hasta llegar al ancestro común (0,2), luego imprimir los nodos que visitó al seguir desde (2,0), seguidos de los nodos que visitó al seguir desde (3,3) , impreso al revés.

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 indicador de retroceso de cualquiera que tenga el mayor costo g, hasta que los dos nodos actuales estén en el mismo lugar.

Sin embargo, vale la pena mencionar que esto es algo extraño. A * no es un recorrido basado en la pila, por lo que no retrocede.

Answer 2

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

Obtuviste demasiado cost=100 allí y, por lo tanto, no puedes retroceder en el camino. Debe aumentar o disminuir el costo en cada paso y llenar solo las celdas que están cerca de las últimas celdas llenas. Eso se puede hacer por recursividad en mapas grandes o escaneando un mapa completo o un cuadro delimitador para el último número lleno en mapas pequeños.

• Busque aquí la implementación mía de C ++ A *

El retroceso

Se puede hacer escaneando vecinos de las celdas de inicio / final después de que el relleno A * se mueva siempre al costo más pequeño / más grande

En este ejemplo, comience a llenar desde (2,0) hasta que se golpee (3,3) y luego retroceda desde (3,2) cost=8 hasta el costo más pequeño (siempre cost-1 para llenado incremental). Si necesita la ruta en orden inverso, comience a llenar desde (3,3) lugar ...

acelerar

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