ai.search.uninformed
Class IDSearcherForDoubleCostFn<S extends SearchStateForDoubleCostFn>

java.lang.Object
  ai.search.SearchEngine
      ai.search.SearchEngineForDoubleCostFn<S>
          ai.search.uninformed.IDSearcherForDoubleCostFn<S>

public class IDSearcherForDoubleCostFn<S extends SearchStateForDoubleCostFn>
extends SearchEngineForDoubleCostFn<S>

This class represents a search engine that traverses a search space by iterative deepening and in depth first order from a given initial state. The initial state, the search limit, and the type of search space must be given to this search engine at construction time. Note that the test for repeated states that is performed during a graph search will only be performed on the predecessors of a newly generated state.

The search must be started using the function doSearch(). Successors of the initial state will then be explored in the reverse order of their depth in the search tree up to a current depth limit. Whenever the search to the current depth limit has exhausted its search space the depth limit is increased and the search is started from scratch. The search will halt when a goal state has been expanded. The goal state and the path to it can then be inspected using the appropriate functions described in the SearchEngineForDoubleCostFn class.

Thus, a typical invocation of an IDSearcherForDoubleCostFn would look something like this:

     SearchEngineForDoubleCostFn s = new IDSearcherForDoubleCostFn(
             initialState, 1000, GRAPH);
     s.doSearch();
     if (s.foundGoalState()) { ... }
 

To continue the search call doSearch() again and the search will be continued as far as possible. Note that this type of search engine will discover the same path to the same goal state multiple times when the depth limit is increased. Paths through a goal state will never be considered.

Author:

Gerhard Wickler

Nested Class Summary

Nested classes/interfaces inherited from class ai.search.SearchEngineForDoubleCostFn

SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S extends SearchStateForDoubleCostFn>

Nested classes/interfaces inherited from class ai.search.SearchEngine

SearchEngine.GraphType

Field Summary

protected int	currentDepthLimit the current depth limit
protected java.util.List<SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S>>	searchStack the stack for unexplored (open) nodes

Fields inherited from class ai.search.SearchEngineForDoubleCostFn

foundGoalNode, initialState

Fields inherited from class ai.search.SearchEngine

doInterrupt, doRepeatTest, searchLimit, searchStarted, traceStream, yieldFrequency

Constructor Summary

IDSearcherForDoubleCostFn(S state, long limit, SearchEngine.GraphType structure)
This constructor creates a new IDSearcherForDoubleCostFn for the given initial state, search limit, and type of search space.

Method Summary

boolean	continuable() This function tests whether the search may be continued.
void	doSearch() This function must be called to start or continue the search.
long	getNrOfExploredStates() This function returns the number of states that have been explored during this search.
long	getNrOfGeneratedStates() This function returns the number of states that have been generated during this search.
void	setDepthLimit(int limit) This function can be used to limit the final depth to which this IDSearcherForDoubleCostFn will go.
void	setInitialDepthLimit(int depth) This function can be used to set the initial depth limit for this IDSearcherForDoubleCostFn.

Methods inherited from class ai.search.SearchEngineForDoubleCostFn

foundGoalState, getGoalState, getInitialState, getSolutionDepth, getSolutionPath, getSolutionPathCost

Methods inherited from class ai.search.SearchEngine

clone, equals, getSearchLimit, hashCode, interrupt, printTrace, setSearchLimit, setTraceStream, setYieldFrequency, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

searchStack

protected java.util.List<SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S extends SearchStateForDoubleCostFn>> searchStack

the stack for unexplored (open) nodes

currentDepthLimit

protected int currentDepthLimit

the current depth limit

Constructor Detail

IDSearcherForDoubleCostFn

public IDSearcherForDoubleCostFn(S state,
                                 long limit,
                                 SearchEngine.GraphType structure)

This constructor creates a new IDSearcherForDoubleCostFn for the given initial state, search limit, and type of search space. Note that the given initial search state must not be null. The search does not start immediately but waits for the function doSearch() to be called.

Parameters:

state - the initial state from which the search space is generated

limit - the initial value for the search limit

structure - TREE or GRAPH, depending on what is to be be searched

Method Detail

setInitialDepthLimit

public void setInitialDepthLimit(int depth)

This function can be used to set the initial depth limit for this IDSearcherForDoubleCostFn. By default the search engine will begin with a depth limit of 0.

Parameters:

depth - the initial depth limit

setDepthLimit

public void setDepthLimit(int limit)

This function can be used to limit the final depth to which this IDSearcherForDoubleCostFn will go. By default the search will go to virtually any depth (Integer.MAX_VALUE).

Parameters:

limit - the maximal depth to which the iteration will go

doSearch

public void doSearch()

This function must be called to start or continue the search. It will only return when one of the following conditions becomes true:

• a goal state has been found: in this case SearchEngineForDoubleCostFn.foundGoalState() will return true, the search will be continuable (continuable() will return true), and SearchEngineForDoubleCostFn.getGoalState() will return a goal state, not null
• the search limit has been reached: in this case SearchEngineForDoubleCostFn.foundGoalState() will return false, the search will not be continuable (continuable() will return false), and SearchEngineForDoubleCostFn.getGoalState() will return null; to make the search continuable the search limit has to be increased using SearchEngine.setSearchLimit(long)
• the search space has been exhausted (up to the depth limit): in this case SearchEngineForDoubleCostFn.foundGoalState() will return false, the search will not be continuable (continuable() will return false), and SearchEngineForDoubleCostFn.getGoalState() will return null

Specified by:

doSearch in class SearchEngine

continuable

public boolean continuable()

This function tests whether the search may be continued. Usually this is the case if there are more search states to be explored and the search limit has not yet been exceeded.

Specified by:

continuable in class SearchEngine

Returns:

true if and only if there are more search states that can be explored

getNrOfExploredStates

public long getNrOfExploredStates()

This function returns the number of states that have been explored during this search. A state counts as explored when the goal test has been performed on the state and its successors have been generated.

Specified by:

getNrOfExploredStates in class SearchEngine

Returns:

the number of nodes that have been closed during this search

getNrOfGeneratedStates

public long getNrOfGeneratedStates()

This function returns the number of states that have been generated during this search. Note that these states may not all be different.

Specified by:

getNrOfGeneratedStates in class SearchEngine

Returns:

the number of states that have been generated during this search