## 304RE: [aima-talk] A* algorithm

Expand Messages
• Dec 17, 2003
Hi,
I have used AIMA version 1, do you use version 1 or not?
I haven't found the inequality of "c(n,a,n') <= h(n) + h(n')" in page 99.
In addition, the scenario is not easy to understand, could you represent it more clearly.

Kind regards/chenyu

-----Original Message-----
From: Imanpreet Singh Arora [mailto:imanpreet_arora@...]
Sent: 2003年12月13日 1:46
To: aima-talk@yahoogroups.com
Subject: [aima-talk] A* algorithm

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

To unsubscribe from this group, send an email to:
aima-talk-unsubscribe@yahoogroups.com