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

554Re: [aima-talk] about A* search

Expand Messages
  • The Geek
    Sep 26, 2005
      I think my version is different from yours, but I
      assume you're talking about the A* search algorithm.

      The proof is in the book a page or so later, but look
      at it the other way for a second - if the path
      estimate were sometimes too high, then based on the
      inflated estimate you might ignore a path that would
      have turned out to have a "short cut" in it. But by
      guaranteeing that the actual cost will always be more
      than your estimate, you're guaranteed never to ignore
      a short cut.

      To put it another way, with an admissible heuristic
      any unexplored path is guaranteed to be worse than or
      equal to it's estimate - never better. Thus when you
      actually explore a path, you're guaranteed that it's
      cost will only get worse. So if you've found an
      actual path solution that's equal to or better than
      the best unexplored path estimates, the actual path
      you've found is guaranteed to be the best because the
      unexplored paths can only get more costly when they're

      I hope that made sense.

      Rob G.

      --- lwudong <wudongs@...> wrote:

      > In page97, line 7:
      > The restriction is to choose an h function that
      > never overestimates
      > the cost to reach the goal. Such an h is called an
      > admissible
      > heuristic. Admissible heuristics are by nature
      > optimistic, because
      > they think the cost of solving the problem is less
      > than it actually is.
      > Can anyone give me more explanation why it always
      > gets the optimial
      > result when it never overestimates the total cost.

      Yahoo! Mail - PC Magazine Editors' Choice 2005
    • Show all 9 messages in this topic