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

about A* search

Expand Messages
  • lwudong
    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.
    Message 1 of 9 , Sep 26, 2005
    View Source
    • 0 Attachment
      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.
    • mohammad assarian
      If we are at node n and my goals are in t1,t2,.... tn. The most aware way from n to Ti shows with H* but we have an estimate of future that we shows with H and
      Message 2 of 9 , Sep 26, 2005
      View Source
      • 0 Attachment
        If we are at node n and my goals are in t1,t2,.... tn. The most aware way from n to Ti shows with H* but we have an estimate of future that we shows with H and the relation between H and H* is H<H* that means our aware to the rest of way is less than the real aware.You can read Artificial Intelligenc book of Nillson .

        M.Assarian
        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! for Good
        Click here to donate to the Hurricane Katrina relief effort.

      • The Geek
        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
        Message 3 of 9 , Sep 26, 2005
        View Source
        • 0 Attachment
          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.

          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
          http://mail.yahoo.com
        • savastinuk
          This makes sense. : ) Can you also explain consistent? Or, better yet, INconsistent? Still talking A*. thanks.... Susan _____ From: aima-talk@yahoogroups.com
          Message 4 of 9 , Sep 27, 2005
          View Source
          • 0 Attachment
            This makes sense. : )
             
            Can you also explain consistent? Or, better yet, INconsistent?
            Still talking A*.
             
            thanks....
            Susan


            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
            explored.

            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
            http://mail.yahoo.com


          • The Geek
            Consistency of heuristics is a little more tricky to explain, since every consistent one is also admissible. If you re not from the U.S., I ll apologize in
            Message 5 of 9 , Sep 27, 2005
            View Source
            • 0 Attachment
              Consistency of heuristics is a little more tricky to
              explain, since every consistent one is also
              admissible.

              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
              is consistent.

              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.

              Rob G.

              --- savastinuk <minnie@...> wrote:

              > This makes sense. : )
              >
              > Can you also explain consistent? Or, better yet,
              > INconsistent?
              > Still talking A*.
              >
              > thanks....
              > Susan
              >
              >
              > _____
              >
              > 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
              > explored.
              >
              > 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
              > http://mail.yahoo.com
              >
              >
              >
              >
              >
              > SPONSORED LINKS
              > Artificial
              >
              <http://groups.yahoo.com/gads?t=ms&k=Artificial+intelligence+software&w1=Art
              >
              ificial+intelligence+software&w2=Artificial+intelligence+in+business&w3=Arti
              >
              ficial+intelligence&w4=Artificial+intelligence+introduction&c=4&s=150&.sig=Z
              > -KgstNm21fXWEV4ASPvHQ> intelligence software
              > Artificial
              >
              <http://groups.yahoo.com/gads?t=ms&k=Artificial+intelligence+in+business&w1=
              >
              Artificial+intelligence+software&w2=Artificial+intelligence+in+business&w3=A
              >
              rtificial+intelligence&w4=Artificial+intelligence+introduction&c=4&s=150&.si
              > g=477uHvbluHUGZv4M3Wsnag> intelligence in business
              > Artificial
              >
              <http://groups.yahoo.com/gads?t=ms&k=Artificial+intelligence&w1=Artificial+i
              >
              ntelligence+software&w2=Artificial+intelligence+in+business&w3=Artificial+in
              >
              telligence&w4=Artificial+intelligence+introduction&c=4&s=150&.sig=LONI6S4JBL
              > JohI0gb7t-Ug> intelligence
              > Artificial
              >
              <http://groups.yahoo.com/gads?t=ms&k=Artificial+intelligence+introduction&w1
              >
              =Artificial+intelligence+software&w2=Artificial+intelligence+in+business&w3=
              >
              Artificial+intelligence&w4=Artificial+intelligence+introduction&c=4&s=150&.s
              > ig=n5dsIRz6BWbukAv5Ru4LcA> intelligence introduction
              >
              >
              > _____
              >
              > YAHOO! GROUPS LINKS
              >
              >
              >
              > * Visit your group "aima-talk
              > <http://groups.yahoo.com/group/aima-talk> " on the
              > web.
              >
              >
              > * To unsubscribe from this group, send an email to:
              > aima-talk-unsubscribe@yahoogroups.com
              >
              <mailto:aima-talk-unsubscribe@yahoogroups.com?subject=Unsubscribe>
              >
              >
              >
              > * 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
            • mohammad assarian
              Dear Sir. When the path estimate is too high, this means that your h function has more less aware(h1) than time your path estimate has more accuracy(h2). when
              Message 6 of 9 , Sep 27, 2005
              View Source
              • 0 Attachment
                Dear Sir.
                When the path estimate is too high, this means that your h function has more less
                aware(h1) than time your path estimate has more accuracy(h2). when h1 is less than h2 , it is natural that h1 develops nodes as number as h2 and perhaps more in your path.So it is possible for h1 that ignore a short cut path as compared with h2 .On the other hand heuristic fuctions have not guarantee for the best path but in more states act very good.
                 
                M.Assarian
                The Geek <guihergeek61@...> wrote:
                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.

                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
                http://mail.yahoo.com


                __________________________________________________
                Do You Yahoo!?
                Tired of spam? Yahoo! Mail has the best spam protection around
                http://mail.yahoo.com

              • savastinuk
                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
                Message 7 of 9 , Sep 27, 2005
                View Source
                • 0 Attachment
                  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,
                  Susan


                  From: aima-talk@yahoogroups.com [mailto:aima-talk@yahoogroups.com] On Behalf Of The Geek
                  Sent: Tuesday, September 27, 2005 1:46 PM
                  To: aima-talk@yahoogroups.com
                  Subject: RE: [aima-talk] about A* search

                  Consistency of heuristics is a little more tricky to
                  explain, since every consistent one is also
                  admissible.

                  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
                  is consistent.

                  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.

                  Rob G.

                  --- savastinuk <minnie@...> wrote:

                  > This makes sense. : )

                  > Can you also explain consistent? Or, better yet,
                  > INconsistent?
                  > Still talking A*.

                  > thanks....
                  > Susan
                  >
                  >
                  >   _____ 
                  >
                  > 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
                  > explored.
                  >
                  > 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
                  > http://mail.yahoo.com
                  >
                  >
                  >
                  >
                  >
                  > SPONSORED LINKS
                  > Artificial
                  >
                  <http://groups.yahoo.com/gads?t=ms&k=Artificial+intelligence+software&w1=Art
                  >
                  ificial+intelligence+software&w2=Artificial+intelligence+in+business&w3=Arti
                  >
                  ficial+intelligence&w4=Artificial+intelligence+introduction&c=4&s=150&.sig=Z
                  > -KgstNm21fXWEV4ASPvHQ> intelligence software
                  > Artificial
                  >
                  <http://groups.yahoo.com/gads?t=ms&k=Artificial+intelligence+in+business&w1=
                  >
                  Artificial+intelligence+software&w2=Artificial+intelligence+in+business&w3=A
                  >
                  rtificial+intelligence&w4=Artificial+intelligence+introduction&c=4&s=150&.si
                  > g=477uHvbluHUGZv4M3Wsnag> intelligence in business
                  > Artificial
                  >
                  <http://groups.yahoo.com/gads?t=ms&k=Artificial+intelligence&w1=Artificial+i
                  >
                  ntelligence+software&w2=Artificial+intelligence+in+business&w3=Artificial+in
                  >
                  telligence&w4=Artificial+intelligence+introduction&c=4&s=150&.sig=LONI6S4JBL
                  > JohI0gb7t-Ug> intelligence      
                  > Artificial
                  >
                  <http://groups.yahoo.com/gads?t=ms&k=Artificial+intelligence+introduction&w1
                  >
                  =Artificial+intelligence+software&w2=Artificial+intelligence+in+business&w3=
                  >
                  Artificial+intelligence&w4=Artificial+intelligence+introduction&c=4&s=150&.s
                  > ig=n5dsIRz6BWbukAv5Ru4LcA> intelligence introduction
                  >      
                  >
                  >   _____ 
                  >
                  > YAHOO! GROUPS LINKS
                  >
                  >
                  >      
                  > *      Visit your group "aima-talk
                  > <http://groups.yahoo.com/group/aima-talk> " on the
                  > web.
                  >  
                  >
                  > *      To unsubscribe from this group, send an email to:
                  >  aima-talk-unsubscribe@yahoogroups.com
                  >
                  <mailto:aima-talk-unsubscribe@yahoogroups.com?subject=Unsubscribe>
                  >
                  >  
                  >
                  > *      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!|_/\|_
                  Does anyone have the implementation of A* search Of Romania Map or some other in prolog or any other reply urgently savastinuk wrote:
                  Message 8 of 9 , Oct 11, 2005
                  View Source
                  • 0 Attachment
                    Does anyone have the implementation of A* search
                    Of Romania Map or some other
                    in prolog or any other
                    reply 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,
                    Susan


                    From: aima-talk@yahoogroups.com [mailto:aima-talk@yahoogroups.com] On Behalf Of The Geek
                    Sent: Tuesday, September 27, 2005 1:46 PM
                    To: aima-talk@yahoogroups.com
                    Subject: RE: [aima-talk] about A* search

                    Consistency of heuristics is a little more tricky to
                    explain, since every consistent one is also
                    admissible.

                    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
                    is consistent.

                    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.

                    Rob G.

                    --- savastinuk <minnie@...> wrote:

                    > This makes sense. : )

                    > Can you also explain consistent? Or, better yet,
                    > INconsistent?
                    > Still talking A*.

                    > thanks....
                    > Susan
                    >
                    >
                    >   _____ 
                    >
                    > 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
                    > explored.
                    >
                    > 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
                    > http://mail.yahoo.com
                    >
                    >
                    >
                    >
                    >
                    > SPONSORED LINKS
                    > Artificial
                    >
                    <http://groups.yahoo.com/gads?t=ms&k=Artificial+intelligence+software&w1=Art
                    >
                    ificial+intelligence+software&w2=Artificial+intelligence+in+business&w3=Arti
                    >
                    ficial+intelligence&w4=Artificial+intelligence+introduction&c=4&s=150&.sig=Z
                    > -KgstNm21fXWEV4ASPvHQ> intelligence software
                    > Artificial
                    >
                    <http://groups.yahoo.com/gads?t=ms&k=Artificial+intelligence+in+business&w1=
                    >
                    Artificial+intelligence+software&w2=Artificial+intelligence+in+business&w3=A
                    >
                    rtificial+intelligence&w4=Artificial+intelligence+introduction&c=4&s=150&.si
                    > g=477uHvbluHUGZv4M3Wsnag> intelligence in business
                    > Artificial
                    >
                    <http://groups.yahoo.com/gads?t=ms&k=Artificial+intelligence&w1=Artificial+i
                    >
                    ntelligence+software&w2=Artificial+intelligence+in+business&w3=Artificial+in
                    >
                    telligence&w4=Artificial+intelligence+introduction&c=4&s=150&.sig=LONI6S4JBL
                    > JohI0gb7t-Ug> intelligence      
                    > Artificial
                    >
                    <http://groups.yahoo.com/gads?t=ms&k=Artificial+intelligence+introduction&w1
                    >
                    =Artificial+intelligence+software&w2=Artificial+intelligence+in+business&w3=
                    >
                    Artificial+intelligence&w4=Artificial+intelligence+introduction&c=4&s=150&.s
                    > ig=n5dsIRz6BWbukAv5Ru4LcA> intelligence introduction
                    >      
                    >
                    >   _____ 
                    >
                    > YAHOO! GROUPS LINKS
                    >
                    >
                    >      
                    > *      Visit your group "aima-talk
                    > <http://groups.yahoo.com/group/aima-talk> " on the
                    > web.
                    >  
                    >
                    > *      To unsubscribe from this group, send an email to:
                    >  aima-talk-unsubscribe@yahoogroups.com
                    >
                    <mailto:aima-talk-unsubscribe@yahoogroups.com?subject=Unsubscribe>
                    >
                    >  
                    >
                    > *      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.

                  • Ivan Villanueva
                    ... If by any other you mean any other language, yes there are A* implementations in Lisp, Python and Java on the Aima webpage, and on my homepage in java
                    Message 9 of 9 , Oct 13, 2005
                    View Source
                    • 0 Attachment
                      On Tue, Oct 11, 2005 at 01:44:06AM -0700, [3!|_/|_ wrote:
                      > Does anyone have the implementation of A* search
                      > Of Romania Map or some other
                      > in prolog or any other

                      If by "any other" you mean any other language, yes there are A* implementations
                      in Lisp, Python and Java on the Aima webpage, and on my homepage in java at:
                      www.artificialidea.com/index.php?page=my_programs

                      Regards,
                      Iván.
                      --
                      Ivan F. Villanueva B.
                      The dream of intelligent machines: www.artificialidea.com
                      Encrypted mail preferred.
                      GPG Key Id: 3FDBF85F 2004-10-18 Ivan-Fernando Villanueva Barrio
                    Your message has been successfully submitted and would be delivered to recipients shortly.