Algorithms in a Nutshell

(^186) | Chapter 7: Path Finding in AI
open.remove( )
Remove the “next” board state to evaluate
closed.insert(INode state)
Add board state to theclosed set
closed.contains(INode state)
Determine whether board state already exists inclosed
open.insert(INode state)
Add board state into theopen set, to be visited later
Since DEPTH-FIRSTSEARCHuses a stack to store theopenset, the remove and
insert operations are performed in constant time. However, ifclosedis simply a
linked list, then the execution ofclosed.contains(INode)may require O(n) perfor-
mance, wherenis the number of states in the closed set. This overhead can be
eliminated by using either a tree or hash structure to store the board states; in
both cases, a key value must be used (as provided by the board state class imple-
mentingINode).
The problem-specific characteristics that affect the performance are the (a)
number of successor board states for an individual board state, and (b) the
ordering of the valid moves. Some games have a large number of potential moves
at each board state, which means that many depth-first paths may be ill-advised.
Also, the way that moves are ordered will affect the overall search. If any heuristic
information is available, make sure that moves most likely leading to a solution
appear earlier in the ordered list of valid moves. We can also take advantage of
symmetries within the board state during the search. Specifically, one can
compute a key from a board state that is the same regardless of the rotation of the
board (either 90, 180, or 270 degrees); additional symmetries exist (horizontal-flip
or vertical-flip). Now, we can’t affect theopenstate set, since for DEPTH-FIRST
SEARCHthis must be a stack-based data structure; however, nothing prevents us
from using such space-saving measures for theclosed state set.
We discuss the performance of DEPTH-FIRSTSEARCHusing a set of three exam-
ples to show how capricious the search is with seemingly slight differences in
state. In each example, 10 tiles are moved from the goal state; Table 7-1 shows the
results of conducting a depth-first search using varying depth bounds. Occasion-
ally DEPTH-FIRSTSEARCHpenetrates quickly to locate a solution, as shown in
Table 7-2; with a depth bound of 8 it finds an eight-move solution for initial state
N1 after searching 25 board states (which is 2 moves better than the 10 moves we
used to create N1 in the first place). Figure 7-7 illustrates the search tree size for
depth-first search as depth increases. In general, the size of the search tree grows
exponentially based upon the branching factorb. For the 8-puzzle, thebranching
factoris between 1.6 and 3.81, based upon where the empty tile is located
(Reinefeld, 1993). The three approximation functions for the size of the search
tree with depth bound ofdfor each of the three initial positions are:
N1: size(n)=0.3429d2.6978
N2: size(n)=.2403d3.2554
N3: size(n)=0.2814*d3.044
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use