Algorithm
Development Kit 1.0

algs.model.searchtree.debug
Class DepthFirstSearch

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

public class DepthFirstSearch
extends java.lang.Object
implements ISearch

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

This search can be terminated with a provided fixed bound.

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

Field Summary
 int numClosed
           
 int numMoves
           
 int numOpen
           
 
Constructor Summary
DepthFirstSearch()
          Construct a depth-first search entity with no fixed depth.
DepthFirstSearch(int bound)
          Construct a depth-fixed search entity.
 
Method Summary
 IDebugSearch debug(IDebugSearch debugger)
          Set the debugger to use when searching (or null to turn off).
 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()
Construct a depth-first search entity with no fixed depth.


DepthFirstSearch

public DepthFirstSearch(int bound)
Construct a depth-fixed search entity.

Parameters:
bound - maximum depth to search
Method Detail

storageType

public void storageType(int type)
Determine structure to use for storing CLOSED set.


debug

public IDebugSearch debug(IDebugSearch debugger)
Set the debugger to use when searching (or null to turn off).


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. Do we avoid generating moves that undo previous move?

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.