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

Re: what is admissible??

Expand Messages
  • fakarim_nsu
    Hi there, admissible heuristic can be any function.But provided that it cannot overestimate the cost to reach the goal!for example in the 8 puzzle problem in
    Message 1 of 3 , Oct 19, 2003
    • 0 Attachment
      Hi there,
      "admissible" heuristic can be any function.But provided that it
      cannot overestimate the cost to reach the goal!for example in the 8
      puzzle problem in the text, a rule of thumb can be it may need 20
      moves to reach the desired goal. Now if ur heuristic takes the
      misarranged tiles as a function or the "manhattan distance" which is
      the distance for a tile from its actual position both of them can be
      considered as "admissible heuristic" because none of them exceeds
      the 20 moves(the example in the book shows they need 7 and 14 steps
      respectively i guess).Thanx



      --- In aima-talk@yahoogroups.com, "hkstudentinuk"
      <hkstudentinuk@y...> wrote:
      > Hi there everyone
      >
      > I am new to AI, just starting a new couse.
      >
      > what is the definition of admissible?? is admissible an algorithem?
      > is the definition of it "never overestimates the cost to reach the
      > goal"?
      >
      > what does admissible means in english in this context?
    • gSm Shourov
      Admissible Heuristic: #Def : A heuristic function (h(n)) with restriction that never overestimates the path cost ( n -- G ). where n = any node/state along
      Message 2 of 3 , Oct 20, 2003
      • 0 Attachment
        Admissible Heuristic:

        #Def : A heuristic function (h(n)) with restriction that never
        overestimates the path cost ('n'-->'G').
        where 'n'= any node/state along the path,
        & 'G'= desired Goal state/locaton.

        #Ex : h SLD (n) = Straight-line distance between n & goal.
        (in the route-finding problem.)

        #This is a monotonic increasing function since it follows
        the Triangle inequality
        (sum of any two sides of a triangle > the third side)
        (QED by Pearl in 1984 )

        #its a function of any kind, not an algorithm





        --- In aima-talk@yahoogroups.com, "fakarim_nsu" <fakarim_nsu@y...>
        wrote:
        > Hi there,
        > "admissible" heuristic can be any function.But provided that it
        > cannot overestimate the cost to reach the goal!for example in the 8
        > puzzle problem in the text, a rule of thumb can be it may need 20
        > moves to reach the desired goal. Now if ur heuristic takes the
        > misarranged tiles as a function or the "manhattan distance" which
        is
        > the distance for a tile from its actual position both of them can
        be
        > considered as "admissible heuristic" because none of them exceeds
        > the 20 moves(the example in the book shows they need 7 and 14 steps
        > respectively i guess).Thanx
        >
        >
        >
        > --- In aima-talk@yahoogroups.com, "hkstudentinuk"
        > <hkstudentinuk@y...> wrote:
        > > Hi there everyone
        > >
        > > I am new to AI, just starting a new couse.
        > >
        > > what is the definition of admissible?? is admissible an
        algorithem?
        > > is the definition of it "never overestimates the cost to reach
        the
        > > goal"?
        > >
        > > what does admissible means in english in this context?
      Your message has been successfully submitted and would be delivered to recipients shortly.