Intro to AI 1: Proving optimality of A* employing graph-search I

Question

Proving optimality of A* employing graph-search I

Christian N · Accepted Answer

Step 1 : If h(n) is consistent, then the values of f (n) along any path are nondecreasing

h(n) ≤ c(n, a, n′) + h(n′)
If h is consistent and n′ is a successor of n, we have
f (n′) = g(n′) + h(n′) = g(n) + c(n, a, n′) + h(n′) ≥ g(n) + h(n) = f (n)

Intro to AI 1

Proving optimality of A* employing graph-search I

Step 1 : If h(n) is consistent, then the values of f (n) along any path are nondecreasing h(n) ≤ c(n, a, n′) + h(n′) If h is consistent and n′ is a successor of n, we have f (n′) = g(n′) + h(n′) = g(n) + c(n, a, n′) + h(n′) ≥ g(n) + h(n) = f (n)

Author