current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.
up vote 3 down vote favorite
1

The A* Algorithm is the optimal (provided the heuristic function is underestimated), complete & admissible (provided some conditions). I know the proofs of admissibility & optimality.

But how do you prove that the A* Algorithm is complete?

share|improve this question
    
interesting factoid if the heuristic function is set to h(x)=0 you get dijkstra –  ratchet freak Mar 17 '13 at 17:32
    
yeah, it is. +1 to the point. Thanks. –  vintesh Mar 17 '13 at 18:17

1 Answer 1

up vote 6 down vote accepted

For a proof of completeness, it is not necessary to look specificially at A*. Any finite graph search algorithm using a node queue where you take one element off, generate all children of that graph node and put them back into the queue is complete, "A*" is just a special case of that kind of algorithms.

Once you got this, it is easy to find a proof of completeness for arbitary graph search by Google, for example, this one:

http://ocw.mit.edu/courses/aeronautics-and-astronautics/16-410-principles-of-autonomy-and-decision-making-fall-2010/lecture-notes/MIT16_410F10_lec04.pdf

The proof itself is not very complex, but IMHO still too long for summarizing it here.

share|improve this answer
    
Thanks. Got the concept. Working on the link provided. –  vintesh Mar 17 '13 at 18:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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