# A* Algorithm Completeness Proof

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?

-
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

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.

-
Thanks. Got the concept. Working on the link provided. – vintesh Mar 17 '13 at 18:08
Meh, summarizing a graph search is easy enough. Super-brief proof by contradiction: Given an algorithm as described above: Let G be the smallest graph for which the algorithm fails. By construction (this step is easier if you define your algorithm recursively, but I'm summarizing, so I'll handwave instead), the algorithm eventually reaches a state where: A) It has discovered a path from START to PEN, where PEN is a node with an edge directed towards END and B) END is in the node queue (or was in it previously). So, it succeeded. Contradiction. – Brian Oct 19 '15 at 18:25
To clarify: We know it found a path from START to PEN because START to PEN is smaller than the smallest graph for which the algorithm fails. – Brian Oct 19 '15 at 18:26
Alternatively, a proof by induction: We can find a path from START to one edge away from start (or from START to START, if you want a one node graph). Any existing graph can be build by adding new edges to this two-node graph, one by one, without making the graph unsolveable. – Brian Oct 19 '15 at 18:28