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

what is admissible??

Expand Messages
  • hkstudentinuk
    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
    Message 1 of 3 , Oct 18, 2003
    • 0 Attachment
      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?
    • 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 2 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 3 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.