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 off(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

A* is complete (finds a solution, if one exists) and also optimal (finds the optimal path to a goal) if:

• the branching factor is finite

• arc costs are > 0

• h(n) is admissible which means an underestimate of the length of the shortest path from n to a goal node.

This property is known as the admissibility of A*

Why A* is Optimally Efficient?

No other optimal algorithm can able to expand fewer nodes than A*.

This is because any algorithm that does not expand every node with f(n) < f* risks to miss the optimal solution.

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(ni) < h(ni + 1), then real-cost(ni) < real-cost(ni + 1).

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

Assume that the path gives 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.

If you are looking to learn more about Artificial Intelligence then you visit Artificial Intelligence(AI) Tutorial. Also, if you are appearing for job profiles of AI Engineer or AI Expert then you can prepare for the interviews on Artificial Intelligence Interview Questions.