Algorithms in a Nutshell

Depth-First Search | 185

Path Finding

in AI

The implementation in Example 7-3 must be careful to store theclosedset using a

structure that efficiently determines whether a board state is already contained

within that set. If, for example, a simple linked list were used, then the accumu-

lated search times in locating an element in the closed set would begin to

dominate the performance of this algorithm. Note that as soon as a successor is

identified as the goal node, the search algorithm terminates (this is true for

BREADTH-FIRSTSEARCH as well).

Consequences

One difference between game trees and search trees is that search trees must store

copies of board states during the search (witness theopenandclosedsets). Search

algorithms over game trees typically execute and undo moves as the search

progresses.

Unbridled DEPTH-FIRSTSEARCHwill blindly search through the search tree,

potentially visiting a tremendous number of nodes without attempting potentially

viable alternative paths. Ironically, using a fixed limit that is too small may result

in very large search trees and fail to arrive at a solution that exists just past the

depth limit of the tree.

Board states are stored to avoid visiting the same state twice. To increase perfor-

mance of the algorithm, we assume there is an efficient function for the board

state to generate a unique key, such that if two board states compute to the same

key, then the board states are equivalent. This notion of equivalence can include

board state characteristics such as symmetry. For example, the board state:

is a 90-degree rotation of the board state:

and could be considered to be equivalent.

DEPTH-FIRSTSEARCHstores less information in itsopenset than BREADTH-FIRST

SEARCH and therefore requires less space.

Analysis

The performance of the algorithm is governed by problem-specific and generic

characteristics. In general, the core operations provided by theopenandclosed

sets may unexpectedly slow the algorithm down, since naïve implementations

would require O(n) performance to locate a board state within the set. The key

operations include:

813

245

76

356

147

82

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