CODEWITHSUNDEEP
searchartificial-intelligenceproof
user10024395
user10024395

Reputation: 1

Proof of optimal efficiency of A* Search

It is mentioned in Norvig's Artificial Intelligence that A* Search is optimally efficient. However, I could not figure out why nor find on the web the proof. Does anyone happen to have a proof?

Upvotes: 1

Views: 1581

Answers (1)

CAFEBABE
CAFEBABE

Reputation: 4101

I hope I'm not doing your homework ;). I only sketch the proof here

First thing you need to see is that A* is optimal. That is it returns the shortest path according to your cost function g. I think this prove is trivial under the assumption that the heuristic h is not overestimating the cost of the solution. If this wouldn't hold optimal efficiency would be meaningless, as A* wouldn't be optimal.

Optimal efficiency: among all optimal algorithms starting from the same name node A* is expending the fewest nodes.

Lets assume an algorithm B does not expand a node n which is A* expanded by A*. By definition for this path g(n)+h(n) <= f where f is the cost of the shortest path. Consider a second problem for which all heuristics values are the same as in the original problem. However, there is a new path to a new goal with total cost smaller f. The assumed algorithm B would expand n hence never reach this new goal. Hence, B wouldn't find this optimal path. Therefore, our original assumption that B is optimal is violated.

Upvotes: 1

Related Questions