¿Cómo implementar el algoritmo AO *?

16

Me di cuenta de que se utilizan diferentes estructuras de datos cuando implementamos algoritmos de búsqueda. Por ejemplo, utilizamos colas para implementar la búsqueda de amplitud, pilas para implementar la búsqueda de profundidad y min-montones para implementar el algoritmo A * . En estos casos, no necesitamos construir 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 construir el árbol de búsqueda explícitamente es la única forma de implementar el algoritmo AO *. ¿Alguien puede proporcionarme una implementación eficiente?

algorithms graphs data-structures search-algorithms Zhang
fuente
3
¡Bienvenido! Recuerde incluir referencias a material no estándar que utilice. Como AO * no tiene un artículo de Wikipedia, un enlace está ciertamente en orden. Espero haber encontrado una buena, por favor verifique.
Rafael
1
¿No es solo un gráfico (con una función que le permite a uno moverse al nodo "siguiente")?
soandos
Sería útil si alguien simplemente esbozara cómo AO * difiere del algoritmo A *. no pude entender eso desde el enlace. en cuanto a la implementación, cualquier estructura para árboles parece razonable ... está atravesando un árbol ¿verdad?
vzn

Respuestas:

1

Con respecto a este artículo, cada vez que expande un nodo en el algoritmo AO * debe retroceder para actualizar el costo estimado de todos sus predecesores.

Cuando utiliza una estructura de datos lineal para contener los nodos, debe atravesar los elementos de datos secuencialmente y solo se puede tomar un elemento de datos directamente (pila, cola, cola de prioridad ...).

En AO * cada vez que se toma un nodo para expansión en función de su costo estimado, el algoritmo itera sobre todos los nodos que son sus predecesores (para actualizar su costo estimado). Eso significa que a veces debe tomar el elemento en función de su costo estimado y, a veces, según su sucesor. No hay un orden de secuencia que pueda cumplir ambas condiciones en el caso general. Probablemente haya una manera de usar estructuras de datos lineales "anidadas", pero debería simplemente imitar una estructura de árbol, y será mejor construir el árbol de búsqueda en su lugar.

Anton
fuente
0

Solo estoy saliendo de esa descripción que vinculaste, pero ¿qué pasa con un BST? Es posible que pueda construirlo para equilibrar nodos no resueltos. Eso podría ahorrarle tiempo en el paso 2 y ayudaría a mantener el tiempo total bajo dependiendo de la cantidad de recorridos. Por supuesto, si equilibraste / ordenaste tu árbol de acuerdo con nodos no resueltos, probablemente serías al menos mejor que una estructura de datos más simplista, manteniendo potencialmente el tiempo logarítmico.

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Univ426
fuente
2
Y puede usted hacer esto?
Raphael
no está tan claro para mí cómo se usaría el BST porque los BST tienen un índice numérico para cada nodo y se usan para colocarlos. ¿Cuál es el índice numérico utilizado?
vzn