Hi I am reading Russell and Norvig's AIMA and I have the following

query.

I am reading section 4.1 regarding A* algorithm, I was

wondering if the triangular inequality that has been shown on page

99 is applicable for

c(n,a,n') <= h(n) + h(n')

also

that is the triangular inequality should be held as a whole.

Furthermore in the following scenario

-------------

| A[ 100] |

_____________

/ \60

/70 \

_____ __________

f=120| B[50]| | C [80] | 140

_____ _________

40 \ /20

_________

| D [80] | f(from B) = 110 + 80 = 190, and f ( from C ) = 80

+ 80 = 160

__________

| 80

________

| Goal |

_________

Now to me the above state space seems to be admissible and

consistent but still the solution path that would be found would

involve D's parent to be B because the first parent would be

accepted. Which is obviously not the best solution because it

involves a total cost of 70+ 40 + 80 = 190 but the path through C

requires 60 + 20 + 80 = 160.

What is the point that I am missing?

--

Imanpreet Singh Arora

isingh AT acm DOT org