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

RE: [aima-talk] about A* search

Expand Messages
  • 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 1 of 9 , Sep 27, 2005
    • 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 2 of 9 , Sep 27, 2005
      • 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 3 of 9 , Sep 27, 2005
        • 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 4 of 9 , Oct 11, 2005
          • 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 5 of 9 , Oct 13, 2005
            • 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.