How to implement the AO * algorithm?

Question

I noticed that some of the data structures are used when we implement search algorithms. For example, we use a queue to implement BFS, stack to implement DFS, and min-heap to implement the A * algorithm. In these cases, we do not need to explicitly build a search tree.

But I cannot find a simple data structure to simulate the AO * algorithm search process. I would like to know if building a search tree explicitly is the only way to implement the AO * algorithm? Can someone provide me with an effective implementation? I really appreciate your help.

Answer 1

Disclaimer: I did not implement AO *, so I could be wrong.

The implementation of AO * should not be different from A *. You are using a bunch, but instead of having only one node, each member should be a vector of nodes (one or more nodes). To some extent, it depends on how you are given (and / or) the rules, but filling the heap should be very simple. Thus, the answer to the first question is no, there is no need to build a tree explicitly, as in the sense that you are not doing this for A *. Remember, the bunch is actually a representation of the search tree, so it can be argued that you are actually building the tree as you move it. Concerning

Can someone provide me with an effective implementation?

you need to show some effort by providing at least some pseudo code or even better a piece of code showing how you attacked the problem. Then we can figure out how to increase efficiency by improving the data structure.