## 306Re: A* algorithm

Expand Messages
• Dec 18, 2003
• 0 Attachment
--- In aima-talk@yahoogroups.com, E etech058 <etech058@o...> wrote:
> 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
>

Thanks, I am using version 2.0. Moreover on page 99 you won't find the
given inequality but the following

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

and it was written that it is a triangular inequality, I am wondering
if the triangular inequality is applicable as whole for all the sides
like is it applicable for the inequality

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

I would try to clarify the scenario, though since I know that the
original indentation that I provided in the message seems to have been
lost.

We have a root node A, and the h(A) is 100.
It has two childern B and C.
g(B) =70 and g(C) = 60
h(B) = 50 and h(C) = 80
so
f(B) = 120
f(C) = 140

Meaning that it would be f(B) that would be expanded, B has a Child
named D and this child is common for the nodes B and C.

Now when B would be expanded the child D would have it's parent set to B.

The cost of getting to D from B and C is respectively 40 and 20 so the
total

g( D through B) is 110
g ( D through C) is 80

Now at this juncture C would be expanded and though D is the child of
C, D's parent would be still set to B because according to section 3.5
the new path would always be rejected.

According to the claims of the authors if h(n) is consitent and
admissible we would certainly find an optimal solution I am not sure
we are able to in this very case.

I belive that if we use the f cost in order to determine the parent of
a node we would certainly find the optimal soution, because for D

f( D through B ) is 190
f ( D through C) is 160

Would the authors and peers be kind to elucidate? I seem to be unable
to relate the equations and principles to a possible graph space that
can clarify me.

--
Imanpreet Singh Arora
• Show all 4 messages in this topic