16
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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 ♦
    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
    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
    Oct 4, 2012 at 17:57

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ And can you do this? $\endgroup$
    – Raphael ♦
    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
    Oct 4, 2012 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.