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

Expand Messages
• 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
explored.

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
> 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
http://mail.yahoo.com
• Show all 9 messages in this topic