Information Technology Reference
In-Depth Information
Figure 9.14.
The best-first search procedure
To find a path from an initial state
S
0
to a goal state
G
:
1.
Maintain a list of states
L
to explore, starting with
L
=[
S
0
]
.
2.
If
L
is empty, then return failure.
3.
Otherwise, select from
L
the state
S
that is
estimated
to be closest to the goal
G
.
4.
If
S
=
G
, then return
success
(and the saved path to
S
0
).
Otherwise, remove
S
from
L
, and add to
L
all states
S
for which
there is a legal move from
S
to
S
(and remember the move involved).
5.
6.
Go to step 2.
produce a sequence of actions that go back from a current state to a start state. (See
exercise 8 at the end of this chapter.)
But there are even more radical changes that can be made. Consider how the
reachable
predicate works to find a path from a start state to a goal state. Suppose
there are two legal moves from a starting state
S
, call them
S
1
and
S
2
. Also, there is a
short path from
S
2
to the goal, but there is no path at all from
S
1
to the goal. Here is
what happens with
reachable
:
1. Generate the state
S
1
using
legal_move
.
2. Recursively look for a path from
S
1
to the goal, eventually failing.
3. Backtrack and generate the next state
S
2
using
legal_move
.
4. Recursively look for a path from
S
2
to the goal, quickly succeeding.
Observe that state
S
2
is considered only after all the options from
S
1
have been
explored. This is called
depth-first search
, since the program looks as deeply as it can
for the goal from
S
1
before it fails and backtracks to consider
S
2
. If the search from
S
1
is large, this could take a lot of time, even if
S
2
is very close to the goal state.
To do better, suppose that for any state, one can
estimate
how far it is from the goal.
This allows a new way of searching, called
best-first search
, summarized in figure 9.14.
At any given point, this search finds the state estimated to be the closest to the goal
and considers legal moves from there. This avoids the problem of searching for the
goal for a long time from state
S
1
even though state
S
2
is very close to the goal.
