2
$\begingroup$

I've been looking for the proof of correctness for the A star (A*) algorithm but none of the texts and websites offer it. Mostly they are talking about the proof of optimality of the A* algorithm. I'm looking for a proof that if the heuristic is admissible, A* will always give an optimal path.

Please help me understand.

To clarify, I want a proof that the path found by A* is correct (i.e., is the cheapest/shortest path to the destination), not a proof that the A* algorithm is optimal (i.e., that any other algorithm that uses the same heuristic will expand at least as many nodes as A*). Also, I'm looking for a proof that only uses the assumption that the heuristic is admissible (without assuming that the heuristic is monotonic or consistent). I've looked in CLRS and haven't found any such proof.

$\endgroup$
  • $\begingroup$ See if this question helps: stackoverflow.com/questions/10195780/…. $\endgroup$ – Yuval Filmus Mar 13 '16 at 16:29
  • $\begingroup$ @YuvalFilmus In the answer, it's given that the heuristic needs to be monotonic. But if that is always true, then A* algorithm would never make any incorrect choices and any node that it expands would definitely have to be on the optimal path to the terminal vertex. As can be seen in this visualization, that does not happen. upload.wikimedia.org/wikipedia/commons/5/5d/… Where am I going wrong? $\endgroup$ – Rahul Kejriwal Mar 13 '16 at 16:56
  • $\begingroup$ Monotonicity is the difference between admissible heuristic and consistent heuristic (Wikipedia terminology). Apparently it's enough for the heuristic to be admissible. The proof of correctness is probably a simple exercise, which is why you don't see it so often. $\endgroup$ – Yuval Filmus Mar 13 '16 at 17:05
  • $\begingroup$ I was wondering if cs.stackexchange.com/questions/44926/… actually addresses your question or not. In case it does not, what is missing there? (so that we can extend that answer to deal with your concerns) $\endgroup$ – Carlos Linares López Mar 14 '16 at 7:39
  • $\begingroup$ My doubt is regarding why the path chosen by A* is correct, i.e., it is the shortest path. At each iteration, A* expands a node with minimum f() as in the explanation there, but the distance from the source or initial terminal that we have estimated for it at this point in time need not be correct. How then can we say, that our algorithm will eventually give the correct shortest path? I am thinking along the lines of the proof for Djikstra's algorithm right now where we show that the estimated distance of the node being expanded is same as the actual distance from the source. $\endgroup$ – Rahul Kejriwal Mar 14 '16 at 17:54
5
$\begingroup$

Check the original paper which talks about its correctness -

Hart, Peter E., Nils J. Nilsson, and Bertram Raphael. "A formal basis for the heuristic determination of minimum cost paths." Systems Science and Cybernetics, IEEE Transactions on 4.2 (1968): 100-107.

See especially Section II and Theorem 1.

$\endgroup$

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.