Algorithms in a Nutshell

Breadth-First Search | 193

Path Finding

in AI

Consequences

BREADTH-FIRSTSEARCHwill blindly search through the search tree, potentially

visiting a tremendous number of nodes while attempting all alternative paths. It is

guaranteed to locate the shortest path to the solution, but to do so it maintains a

large set ofopenboard states. Fortunately, theopenboard states are accessed as a

queue, so the removal and insertion can be performed in constant time.

Analysis

As with DEPTH-FIRSTSEARCH, the performance behavior of the algorithm is

governed by problem-specific and generic characteristics. The same analysis

regarding the generic characteristics of DEPTH-FIRSTSEARCHapplies here, and

the only difference is the size of the set ofopenboard states. BREADTH-FIRST

// Start from the initial state

INodeSet open = StateStorageFactory.create(StateStorageFactory.QUEUE);

open.insert(initial.copy( ));

// states we have already visited.

INodeSet closed = StateStorageFactory.create(StateStorageFactory.HASH);

while (!open.isEmpty( )) {

INode n = open.remove( );

closed.insert(n);

// All successor moves translate into appended OPEN states.

DoubleLinkedList<IMove> moves = n.validMoves( );

for (Iterator<IMove> it = moves.iterator( ); it.hasNext( ); ) {

IMove move = it.next( );

// make move on a copy

INode successor = n.copy( );

move.execute(successor);

// If already visited, search this state no more

if (closed.contains(successor) != null) {

continue;

}

// Record previous move for solution trace. If solution, leave

// now, otherwise add to the OPEN set.

successor.storedData(new Transition(move, n));

if (successor.equals(goal)) {

return new Solution (initial, successor);

}

open.insert(successor);

}

}

return new Solution (initial, goal, false); // No solution.

}

Example 7-4. Breadth-First Search implementation (continued)

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