Menu
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.
650
AO* Algorithm When a problem can be divided into a set of sub problems, where each sub problem can be solved separately and a combination of these will be a solution, AND-OR graphs or AND - OR trees are used for representing the solution. The decomposition of the problem or problem reduction generates AND arcs.
Introduction: AO* algorithm is a best first search algorithm. AO* algorithm uses the concept of AND-OR graphs to decompose any complex problem given into smaller set of problems which are further solved.
AO* has rarely been used in practical applications, to my knowledge. It is useful for searching game trees, problem solving etc. but in most cases more domain specific search algorithms (e.g. alpha-beta pruning for game trees, general or domain specific planning algorithms) are used instead.
AO* Search: (And-Or) Graph The main difference lies in the way termination conditions are determined, since all goals following an AND nodes must be realized; where as a single goal node following an OR node will do. So for this purpose we are using AO* algorithm.
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.
116
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
