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.

Answer 2

We follow these key points in order to formally demonstrate A* finds the shortest path given an admissible heuristic-a heuristic that never overestimates the true cost:

Admissibility Assumption: The heuristic h(n) is admissible, in other words, h(n)≤h*(n) (true cost from node n to the goal). The result is that f(n)=g(n)+h(n) will always be less than or equal to the true cost for a path.

Optimal Path Assumption: Let P be the optimal path from the start node s to the goal G with a cost g*(G). We have to prove that A* will always return g*(G) as the solution.

Proof by Contradiction:Assume that A* finds a non-optimal path 'P′ to G with g(P′)>g*(G) However, since h is admissible the estimated cost f(n) along a path in P is always strictly less than the cost along some nonoptimal path 'P′.

As A* expands the nodes according to increasing order of f(n), before exploring P’ along which P is a substring, A* must explore P - contradicting assumption.

Conclusion: The expansion of nodes based on minimum f(n) and the admissible heuristic ensures that A* approaches the goal via the lowest cost path, which is one proof of optimality.