, LOCAL SEARCH
from start state to
Local search
algorithms operate by searching a
•
neighboring states , without
keeping track of the paths ,
nor the
set of states that have been reached
•
These algorithms are not systematic [they
might never explore a portion
of the search space where a solution actually resides]
advantages
:
2 key
•
→ (1) Use
very little memory
→ (2) Often find reasonable solutions in large or infinite state
spaces for which systematic algorithms are unsuitable
Local search
algorithms can also solve optimization problems in which the
•
,
aim is to find the best state accordingto an objective function
•
If state corresponds to an objective function , then the aim is to
find the highest peak a maximum and we call the process
global
- -
hill -
climbing
•
If elevation corresponds to cost then the aim is to find the lowest
,
valley -
a
global minimum and we call it gradient descent
-
HILL CLIMBING
Hill climbing does not look ahead beyond the immediate neighbors of
•
the current state
•
start :
whenever
•
Repeat :
move to the best neighboring state [ heads in the direction that
provides the steepest ascent]
•
If no
neighbor is better than current
,
quit
from start state to
Local search
algorithms operate by searching a
•
neighboring states , without
keeping track of the paths ,
nor the
set of states that have been reached
•
These algorithms are not systematic [they
might never explore a portion
of the search space where a solution actually resides]
advantages
:
2 key
•
→ (1) Use
very little memory
→ (2) Often find reasonable solutions in large or infinite state
spaces for which systematic algorithms are unsuitable
Local search
algorithms can also solve optimization problems in which the
•
,
aim is to find the best state accordingto an objective function
•
If state corresponds to an objective function , then the aim is to
find the highest peak a maximum and we call the process
global
- -
hill -
climbing
•
If elevation corresponds to cost then the aim is to find the lowest
,
valley -
a
global minimum and we call it gradient descent
-
HILL CLIMBING
Hill climbing does not look ahead beyond the immediate neighbors of
•
the current state
•
start :
whenever
•
Repeat :
move to the best neighboring state [ heads in the direction that
provides the steepest ascent]
•
If no
neighbor is better than current
,
quit
