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

239Re: what is admissible??

Expand Messages
  • gSm Shourov
    Oct 20, 2003
      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...>
      > 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
      > the distance for a tile from its actual position both of them can
      > 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
      > > is the definition of it "never overestimates the cost to reach
      > > goal"?
      > >
      > > what does admissible means in english in this context?
    • Show all 3 messages in this topic