How to implement AO* algorithm?

Question

I've noticed that some data structures are used when we implement search algorithms. For example, we use the 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 the AO* algorithm? Can anybody provide me an efficient implementation? I really appreciate your help.

Answer 1

Here is the algorithm for AO*:

1. Initialize the graph to start node

2. Negotiate the graph following the current path accumulating nodes that have not yet been expanded or solved

3. Then choose any of these nodes and expand it and if it has no successors call this value FUTILITY otherwise calculate only f' for each of the successors.

4. If f' is 0 then consider the node as SOLVED

5. Change the value of f' for the recently created node to display its successors by backpropagation.

6. Anywhere possible use the most assuring routes and if a node is marked as SOLVED then mark the parent node as SOLVED.

7. If starting node is SOLVED or a value greater than FUTILITY, stop, else repeat from 2.

For the implementation of AO*, refer to the following link:

https://www.brainkart.com/article/AO--Search(Graph)--Concept,-Algorithm,-Implementation,-Advantages,-Disadvantages_8884/

For more information on AI, you can visit Artificial Intelligence Tutorial and join AI Course.