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

557FW: [aima-talk] about A* search

Expand Messages
  • savastinuk
    Sep 27, 2005
      Hi again,
      I apologize for interrupting (can you do that in email?!)
      Before answering me, the person who asked the original question should be satisfied with the answers. : )

      From: savastinuk [mailto:minnie@...]
      Sent: Tuesday, September 27, 2005 7:04 AM
      To: 'aima-talk@yahoogroups.com'
      Subject: RE: [aima-talk] about A* search

      This makes sense. : )
      Can you also explain consistent? Or, better yet, INconsistent?
      Still talking A*.

      From: aima-talk@yahoogroups.com [mailto:aima-talk@yahoogroups.com] On Behalf Of The Geek
      Sent: Monday, September 26, 2005 6:03 PM
      To: aima-talk@yahoogroups.com
      Subject: Re: [aima-talk] about A* search

      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