I have noticed that different data structures are used when we implement search algorithms. For example, we use queues to implement breadth first search, stacks to implement depth-first search and min-heaps to implement the A* algorithm. In these cases, we do not need to construct the search tree explicitly.
But I can not 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?
-
3$\begingroup$ Welcome! Please remember to include references to non-standard material you use. As AO* has no Wikipedia article, a link is certainly in order. I hope I found a good one, please check. $\endgroup$Raphael– Raphael2012年04月04日 05:50:43 +00:00Commented Apr 4, 2012 at 5:50
-
1$\begingroup$ Isn't it just a graph (with a function that allows one to move to the "next" node)? $\endgroup$soandos– soandos2012年04月04日 11:37:10 +00:00Commented Apr 4, 2012 at 11:37
-
$\begingroup$ it would help if someone just sketched out how AO* differs from the A* algorithm. couldnt quite figure that out from the link. as for implementation, any structure for trees seems reasonable.... it is traversing a tree right? $\endgroup$vzn– vzn2012年10月04日 17:57:36 +00:00Commented Oct 4, 2012 at 17:57
2 Answers 2
Regarding this article every time you expand a node in the AO* algorithm you must go backwards to update all of its predecessors’ estimated cost.
When you use linear data structure to contain the nodes you must traverse the data elements sequentially and only one data element can be directly taken (stack, queue, priority queue ...).
In AO* each time a node is taken for expansion based on its estimated cost the algorithm iterates over all of the nodes that are its predecessors(to update their estimated cost). That means that sometimes you should take element based on its estimated cost and sometimes based on its successor. There is no sequence order that can meet both of these conditions in the general case. Probably there is a way to use "nested" linear data structures, but it should just imitate a tree structure, and it will be better to build the search tree instead.
I'm just going off that description you linked to, but what about a BST? You might be able to construct it to balance out unsolved nodes. That could save you time on step 2, and would help keep the overall time down depending on the number of traversals. Of course, if you balanced/sorted your tree according to unsolved nodes, you'd probably be at least better than a more simplistic data structure, potentially keeping in/around logarithmic time.
http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
-
2$\begingroup$ And can you do this? $\endgroup$Raphael– Raphael2012年06月19日 19:18:17 +00:00Commented Jun 19, 2012 at 19:18
-
$\begingroup$ its not so clear to me how the BST would be used because BSTs have a numerical index for each node & used to place them. what is the numerical index used? $\endgroup$vzn– vzn2012年10月04日 17:58:40 +00:00Commented Oct 4, 2012 at 17:58
Explore related questions
See similar questions with these tags.