¿Cómo implementar el algoritmo AO *?

Question

He notado que algunas estructuras de datos se usan cuando implementamos algoritmos de búsqueda. Por ejemplo, usamos la cola para implementar BFS, apilar para implementar DFS y min-heap para implementar el algoritmo A *. En estos casos, no es necesario que construyamos el árbol de búsqueda explícitamente.

Pero no puedo encontrar una estructura de datos simple para simular el proceso de búsqueda del algoritmo AO *. Me gustaría saber si la construcción explícita del árbol de búsqueda es la única forma de implementar el algoritmo AO *. ¿Alguien puede proporcionarme una implementación eficiente? Realmente aprecio tu ayuda.

Answer 1

Descargo de responsabilidad: No he implementado AO *, por lo tanto, podría estar equivocado.

La implementación de AO * no debe ser tan diferente de A *. Utiliza un montón, pero en lugar de tener un solo nodo, cada miembro debe ser un vector de nodos (uno o más nodos). Hasta cierto punto, depende de cómo se le otorguen las reglas (y/o), pero poblar el montón debería ser realmente fácil. Entonces la respuesta a la primera pregunta es no, no hay necesidad de construir el árbol explícitamente en el sentido de que no lo haga para A *. Recuerde que un montón es realmente una representación de un árbol de búsqueda, por lo que podría argumentarse que está realmente construyendo el árbol a medida que lo recorre. Con respecto a

¿Alguien puede proporcionarme una implementación eficiente?

necesita mostrar un poco de esfuerzo al proporcionar al menos un pseudocódigo o incluso mejor un fragmento de código que muestra cómo ha atacado el problema. Luego, podemos encontrar sugerencias sobre cómo aumentar la eficiencia mejorando la estructura de datos.