How to implement AO* algorithm?

Question

I've noticed that some data structures are used when we implement search algorithms. For example, we use queue to implement BFS, stack to implement DFS and min-heap to implement the A* algorithm. In these cases, we don't need to construct the search tree explicitly.

But I can't find a simple data structure to simulate the searching process of the AO* algorithm. I would like to know if constructing the search tree explicitly is the only way to implement AO* algorithm? Can anybody provide me an efficient implementation? I really appreciate your help.

Answer 1

Disclaimer: I haven't implemented AO*, hence i might be wrong.

Implementing AO* shouldn't be that different from A*. You use a heap but instead of having just a single node, each member should be a vector of nodes (one or more nodes). To some degree it depends how the (and-or) rules are given to you, but populating the heap should be really easy. So the answer to the first question is no, there is no need to construct the tree explicitly as in the sense you don't do so for A*. Remember a heap actually a representation of a search tree, so one could argue you're really constructing the tree as you traverse it. Regarding

Can anybody provide me an efficient implementation?

you need to show some effort by providing at least some pseudocode or even better a piece of code showing use how you have attacked the problem. Then we can come up wit suggestions how to increase the efficiency by improving the data structure.