A * Optimality with sequential heuristics

Question

Where can I find the proof for the following theorem:

Theorem. If h (n) is consistent, A * using GRAPH-SEARCH is optimal

Thanks.

Answer 1

You can find it in this book on page 95-97:

http://www.amazon.com/Artificial-Intelligence-Modern-Approach-3rd/dp/0136042597/ref=sr_1_1?ie=UTF8& S = books & QID = 1295781411 & cf = 8-1

The main outline of the proof:

First we define these functions:

g (n) = cost to reach node from start of node

f (n) = g (n) + h (n)

Steps:

• To establish that the values ​​of f (n) along any path are non-decreasing if h (n) is consistent.

• Prove that whenever A * selects a node for expansion, the optimal path to that node has been found.

Step 1 follows directly from the definition of the sequence.

Step 2 is proved by the fact that if this were not true, then on the optimal path from the beginning of node to n there should have been another boundary node n ', but this cannot be, as the paths are non-decreasing and, therefore, node will have a lower cost f than n. That is, f (n) = g (n) + h (n)> f (n ') = g (n') + h (n ')

Answer 2

read this page

Two steps to prove:

1- Establish that the values of f(n) along any path are nondecreasing, if h(n) is consistent. 2- Prove that whenever A* selects a node for expansion, the optimal path to that node has been found.