## 301A* algorithm

Expand Messages
• Dec 12, 2003
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
• Show all 4 messages in this topic