Algorithms in a Nutshell

(^184) | Chapter 7: Path Finding in AI
Each board state stores a reference, called aDepthTransition, that records (a) the
move that generated it, (b) the previous state, and (c) the depth from the initial
position. The algorithm generates copies of each board state since the moves are
applied directly to the boards and not undone.
Example 7-3. Depth-First Search implementation
public Solution search(INode initial, INode goal) {
// If initial is the goal, return now.
if (initial.equals(goal)) { return new Solution (initial, goal); }
INodeSet open = StateStorageFactory.create(OpenStateFactory.STACK);
open.insert(initial.copy( ));
// states we have already visited.
INodeSet closed = StateStorageFactory.create(OpenStateFactory.HASH);
while (!open.isEmpty( )) {
INode n = open.remove( );
closed.insert(n);
DepthTransition trans = (DepthTransition) n.storedData( );
// All successor moves translate into appended OPEN states.
DoubleLinkedList moves = n.validMoves( );
for (Iterator it = moves.iterator( ); it.hasNext( ); ) {
IMove move = it.next( );
// Execute move on a copy since we maintain sets of board states
INode successor = n.copy( );
move.execute(successor);
// If already visited, try another state
if (closed.contains(successor) != null) { continue; }
int depth = 1;
if (trans != null) { depth = trans.depth+1; }
// Record previous move for solution trace. If solution, leave now,
// otherwise add to the OPEN set if still within depth bound
successor.storedData(new DepthTransition(move, n, depth));
if (successor.equals(goal)) {
return new Solution (initial, successor);
}
if (depth < depthBound) { open.insert (successor); }
}
}
return new Solution (initial, goal, false); // No solution
}
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
Licensed by
Ming Yi