Browse Groups

• 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
View Source
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.
>
> is the definition of it "never overestimates the cost to reach the
> goal"?
>
> what does admissible means in english in this context?
• 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
View Source

#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.
> >
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.