Proof of A* algorithm's optimality when heuristics always underestimates

Question

I understand why A* algorithm always gives the most optimal path to a goal state when the heuristic always underestimates, but I can't create a formal proof for it.

As far as I understand, for each path considered as it goes deeper and deeper the accuracy of f(n) increases until the goal state, where it is 100% accurate. Also, no incorrect paths are ignored, as estimation is less than the actual cost; thus leading to the optimal path. But how should I create a proof for it?

Answer 1

The main idea of the proof is that when A* finds a path, it has a found a path that has an estimate lower than the estimate of any other possible paths. Since the estimates are optimistic, the other paths can be safely ignored.

Also, A* is only optimal if two conditions are met:

1. The heuristic is admissible, as it will never overestimate the cost.

2. The heuristic is monotonic, that is, if h(n_i) < h(n_{i + 1}), then real-cost(n_i) < real-cost(n_{i + 1}).

---

You can prove the optimality to be correct by assuming the opposite, and expanding the implications.

Assume that the path give by A* is not optimal with an admissible and monotonic heuristic, and think about what that means in terms of implications (you'll soon find yourself reaching a contradiction), and thus, your original assumption is reduced to absurd.

From that you can conclude that your original assumption was false, that is, A* is optimal with the above conditions. Q.E.D.

Answer 2

Consider that last step, the one that completes the optimal path.

Why must A* choose that path? Or, put another way, why must A* avoid choosing a sub-optimal path that reaches the goal?

Hint: this is the reason the heuristic needs to be admissible. Note that it is ok to choose a sub-optimal path, so long as it doesn't complete the path (why?).

That should give you some idea of how to fashion a proof.