Expand Messages
• 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 1 of 3 , Oct 20, 2003
• 0 Attachment

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