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?
1
-
interesting factoid if the heuristic function is set to h(x)=0 you get dijkstra– ratchet freakMar 17, 2013 at 17:32
Add a comment
|
1 Answer
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:
The proof itself is not very complex, but IMHO still too long for summarizing it here.
answered Mar 17, 2013 at 18:00
-
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.– BrianOct 19, 2015 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.– BrianOct 19, 2015 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.– BrianOct 19, 2015 at 18:28