569RE: [aima-talk] about A* search
- Oct 11 1:44 AMDoes anyone have the implementation of A* searchOf Romania Map or some otherin prolog or any otherreply urgently
savastinuk <minnie@...> wrote:Rob,Thanks so much! This helps me with a homework problem that I was completely stumped on. I'll cite your letter, as our teacher asked us to do if we get help with an answer.Your admissible but inconsistent trip example went right past where I live, near Philadelphia. : )regards,SusanConsistency of heuristics is a little more tricky to
From: firstname.lastname@example.org [mailto:email@example.com] On Behalf Of The Geek
Sent: Tuesday, September 27, 2005 1:46 PM
Subject: RE: [aima-talk] about A* search
explain, since every consistent one is also
If you're not from the U.S., I'll apologize in advance
for the following example....
Lets say you're trying to get from New York to L.A. by
car - forget the fact that it would now cost you a
small fortune to do so. A consistent heuristic is one
where the estimate to get from New York to L.A. must
be equal to or smaller than the actual cost to get
from New York to any other city **plus** the estimate
to get from that city to L.A. In other words, if you
drive from New York to Chicago, then estimate the
distance from Chicago to L.A. you're not supposed to
get a smaller answer than your original estimate. If
you use straight-line distance, it's easy to see this
Admissible heurstics must guarantee the estimate is no
larger than the actual cost turns out to be.
Consistent heuristics must also guarantee the "revised
estimate" (the sum of the actual distance traveled so
far plus the estimate of what you've got remaining)
never goes down as you explore the path.
You have to get kind of goofy to find things that are
admissible but not consistent - taking the
straight-line distance divided by the number of
letters in the city name for example. The estimate is
guaranteed to be low (since it's always less than the
straight-line distance), and thus is admissible. When
you start at New York your estimate would be 2400/7 =
342.86. If you drove 95 miles to Philadelphia, you're
estimate from Philadelphia to L.A. would be 2320 / 12
= 193.33. Adding that back to the 95 miles you drove
from New York we see that we now think we can get from
New York to L.A. by way of Philadelphia for an
estimated cost of 193.33 + 95 = 288.33, less than our
original estimate of 342.86, thus demonstrating that
the heuristic is not consistent.
--- savastinuk <minnie@...> wrote:
> This makes sense. : )
> Can you also explain consistent? Or, better yet,
> Still talking A*.
> From: firstname.lastname@example.org
> [mailto:email@example.com] On Behalf
> Of The Geek
> Sent: Monday, September 26, 2005 6:03 PM
> To: firstname.lastname@example.org
> 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
> 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
> than your estimate, you're guaranteed never to
> a short cut.
> To put it another way, with an admissible heuristic
> any unexplored path is guaranteed to be worse than
> equal to it's estimate - never better. Thus when
> 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
> unexplored paths can only get more costly when
> 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
> SPONSORED LINKS
> -KgstNm21fXWEV4ASPvHQ> intelligence software
> g=477uHvbluHUGZv4M3Wsnag> intelligence in business
> JohI0gb7t-Ug> intelligence
> ig=n5dsIRz6BWbukAv5Ru4LcA> intelligence introduction
> YAHOO! GROUPS LINKS
> * Visit your group "aima-talk
> <http://groups.yahoo.com/group/aima-talk> " on the
> * To unsubscribe from this group, send an email to:
> * Your use of Yahoo! Groups is subject to the
> Yahoo! Terms of Service
> <http://docs.yahoo.com/info/terms/> .
Yahoo! Mail - PC Magazine Editors' Choice 2005
http://mail.yahoo.com[3 ! |_ /\ |_
Yahoo! Music Unlimited - Access over 1 million songs. Try it free.
- << Previous post in topic Next post in topic >>