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?