A* Algorithm from AIMA

From: Gagan (gaganoops_at_hotmail.com)
Date: 12/13/03 

Date: Sat, 13 Dec 2003 01:56:19 GMT

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
[ comp.ai is moderated.  To submit, just post and be patient, or if ]
[ that fails mail your article to <comp-ai@moderators.isc.org>, and ]
[ ask your news administrator to fix the problems with your system. ]