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?
A* Algorithm Completeness Proof
algorithms;algorithm analysis;a star
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.pdfThe proof itself is not very complex, but IMHO still too long for summarizing it here.