The A* Guarantee
A* guarantees to find optimal solution
Proof: suppose not, and we derive a contradiction
- Then there is a solution with higher cost found first
- must be earlier in list than precursor of optimal solution
- heuristic cost = true cost (by guarantee 2)
- true cost of worse solution > true cost of optimal
- true cost of optimal ? heuristic cost of precursor (guar. 1)
- ? true cost of worse solution > heuristic cost of precursor
- ? precursor of optimal earlier in list than worse solution
- Contradiction, w5 (which was what was wanted)