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

301A* algorithm

Expand Messages
  • Imanpreet Singh Arora
    Dec 12, 2003
    • 0 Attachment
      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