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.