Proof of the optimality of the algorithm A *, when the heuristic always underestimates

Question

I understand why the A * algorithm always provides the optimal path to the state of the target, when the heuristic always underestimates it, but I cannot create a formal proof for it.

As far as I understand, for each path that is considered as it goes deeper and deeper, the accuracy f(n) increases to the state of the target, where it is 100% accurate. In addition, no wrong paths are ignored because the valuation is less than the actual cost; leading to an optimal path. But how do I create evidence?

Answer 1

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

In addition, A * is only optimal if two conditions are satisfied:

• Heuristics are acceptable because they will never overestimate the value.

• Heuristic is monotonous, i.e. if h (n _i ) <h (n _{i + 1} ), then the real cost (n _i ) <real-cost (n _{i + 1} ).

---

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

Assume that the path given by A * is not optimal with a valid and monotonous heuristic, and think about what this means in terms of consequences (you will soon find that you will reach a contradiction), and thus your initial assumption is absurd.

From this we can conclude that your initial assumption was false, that is, A * is optimal with the above conditions. QED

Answer 2

Consider the last step that completes the optimal path.

Why does A * choose this path? Or, in other words, why does A * avoid choosing the suboptimal path that reaches the goal?

Hint : this is the reason why heuristics should be valid. Please note that it is normal to choose a suboptimal path if it does not complete the path (why?).

This should give you some insight into how to create evidence.