Algorithm
Development Kit 1.0

algs.model.searchtree
Class DepthFirstSearch

java.lang.Object
  extended by algs.model.searchtree.DepthFirstSearch
All Implemented Interfaces:
ISearch

public class DepthFirstSearch
extends java.lang.Object
implements ISearch

Given an initial state, a target goal state, expand in breadth-first manner all available moves until the target goal state is reached.

This search approach uses a Stack to store the OPEN set, to expand the most recently added board states, until the depth limit is reached.

Note that different performance can be obtained by setting the closedStorage appropriately. If set to StateStorageFactory.HASH then performance benefits will be seen. If set to StateStorageFactory.TREEWITHKEY then the boardstate Key will be used to differentiate boards. With board states that exhibit rotational symmetry, this method will achieve faster search times.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Field Summary
 int numClosed
           
 int numMoves
           
 int numOpen
           
 
Constructor Summary
DepthFirstSearch()
          Depth-First with no bound.
DepthFirstSearch(int bound)
          Initiate the Depth First Search with the given fixed-depth bound to search.
 
Method Summary
 Solution search(INode initial, INode goal)
          Initiate the search for the target state.
 void storageType(int type)
          Determine structure to use for storing CLOSED set.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

numMoves

public int numMoves

numOpen

public int numOpen

numClosed

public int numClosed
Constructor Detail

DepthFirstSearch

public DepthFirstSearch()
Depth-First with no bound.


DepthFirstSearch

public DepthFirstSearch(int bound)
Initiate the Depth First Search with the given fixed-depth bound to search.

Parameters:
bound - fixed depth to which to search.
Method Detail

storageType

public void storageType(int type)
Determine structure to use for storing CLOSED set. Possible types are drawn from StateStorageFactory

Parameters:
type -

search

public Solution search(INode initial,
                       INode goal)
Initiate the search for the target state. Store with each INode object a Transition (Move m, INode prev) so we can retrace steps to the original solution.

Specified by:
search in interface ISearch
Parameters:
initial - the initial board state
goal - the final board state

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.