Java Reference
In-Depth Information
Node
in
Listing 8.14
represents a position that has been reached through some series of
moves, holding a reference to the move that created the position and the previous
Node
. Fol-
lowing the links back from a
Node
lets us reconstruct the sequence of moves that led to the
current position.
SequentialPuzzleSolver
in
Listing 8.15
shows a sequential solver for the puzzle
framework that performs a depth-first search of the puzzle space. It terminates when it finds
a solution (which is not necessarily the shortest solution).
Rewriting the solver to exploit concurrency would allow us to compute next moves and eval-
uate the goal condition in parallel, since the process of evaluating one move is mostly in-
dependent of evaluating other moves. (We say “mostly” because tasks share some mutable
state, such as the set of seen positions.) If multiple processors are available, this could reduce
the time it takes to find a solution.
tends
Node
and implements
Runnable
. Most of the work is done in
run
: evaluating the
set of possible next positions, pruning positions already searched, evaluating whether success
has yet been achieved (by this task or by some other task), and submitting unsearched posi-
tions to an
Executor
.
To avoid infinite loops, the sequential version maintained a
Set
of previously searched po-
sitions;
ConcurrentPuzzleSolver
uses a
ConcurrentHashMap
for this purpose.
This provides thread safety and avoids the race condition inherent in conditionally updating a
shared collection by using
putIfAbsent
to atomically add a position only if it was not pre-
viously known.
ConcurrentPuzzleSolver
uses the internal work queue of the thread
pool instead of the call stack to hold the state of the search.
