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

304RE: [aima-talk] A* algorithm

Expand Messages
  • E etech058
    Dec 17, 2003
    • 0 Attachment
      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




      Yahoo! Groups Links

      To visit your group on the web, go to:
      http://groups.yahoo.com/group/aima-talk/

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

      Your use of Yahoo! Groups is subject to:
      http://docs.yahoo.com/info/terms/
    • Show all 4 messages in this topic