4

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
  • 2
    Does this not belong on CS stack exchange instead? this is not a Software Engineering question at all, and is possibly a duplicate on either SO se or CS se. – opa Oct 5 '17 at 13:44
8

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 from, 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.

  • 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

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.