Loading ...
Sorry, an error occurred while loading the content.

309RE: [aima-talk] Re: A* algorithm

Expand Messages
  • E etech058
    Dec 19, 2003
      Hello Imanpreet,
      I have read your email carefully, and then read the AIMA book again. My idea is as follows:
      1. A* will find the optimal (best) solution. It is correct.
      2. Your idea has one implicit assumption, which is not same as the book. That's you assume that "GOAL-TEST(NODE)" check will be run immediate after the "EXPAND" function. The correct one (AIMA books "GENERAL-SEARCH" pceudo-code) is "EXPAND", then "QUEUE-FN", then "GOAL-TEST".
      2.1 Your above implicit assumption means that you doesn't give the more chance to "A*" for finding more optimal solution.
      2.2 Explain by your example. After "Node B f(B)=120" is expanded, in the A* queue, 2 nodes exists. One is "Node D f(D)=180", the other is "Node C f(C)=140". Then (Please look at "GENERAL-SEARCH" pseudo-code) function "QUEUING-FN" will work. It will produce list which "Node B f(B)=120" is a header. In the next loop, "Node B" will be expanded. It means that although the goal of "Node D" has been founded, the A* will continue to run until it finds a optimal solution.
      3. I just think in the actual programming, your implicit assumption will be used. It means comparing between found pure optimal (A*) solution, the quick and efficient algorithm is more important.

      Kind regards/chenyu

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

      --- 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

      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
      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

      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

      To unsubscribe from this group, send an email to:

      Yahoo! Groups Links

      To visit your group on the web, go to:

      To unsubscribe from this group, send an email to:

      Your use of Yahoo! Groups is subject to:
    • Show all 4 messages in this topic