ai.search.informed
Class RBFSearcherForIntCostFn<S extends SearchStateForIntCostFn>

java.lang.Object
  ai.search.SearchEngine
      ai.search.SearchEngineForIntCostFn<S>
          ai.search.informed.BestFirstSearcherForIntCostFn<S>
              ai.search.informed.RBFSearcherForIntCostFn<S>

public class RBFSearcherForIntCostFn<S extends SearchStateForIntCostFn>
extends BestFirstSearcherForIntCostFn<S>

This class represents a search engine that traverses a search space from a given initial state using the recursive best-first search algorithm (RBFS). The initial state and the heuristic function must be given to this search engine at construction time. Note that the test for repeated states will here only be performed on the predecessors of a newly generated state.

Now the search can be started using the function doSearch(). Successors of the initial state will then be explored. 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 SearchEngineForIntCostFn class.

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

     SearchEngineForIntCostFn s = new RBFSearcherForIntCostFn(
             initialState, heuristic, 1000, TREE);
     s.doSearch();
     if (s.foundGoalState()) { ... }
 

To continue the search call doSearch() again and the search will be continued as far as possible.

Author:

Gerhard Wickler

Nested Class Summary

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

SearchEngineForIntCostFn.SearchNodeForIntCostFn<S extends SearchStateForIntCostFn>

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

SearchEngine.GraphType

Field Summary

protected int[]	fValues the f-Values for the nodes in the stack
protected SearchEngineForIntCostFn.SearchNodeForIntCostFn<S>[]	searchStack the stack for unexplored (open) nodes

Fields inherited from class ai.search.informed.BestFirstSearcherForIntCostFn

dfTendency, h, hweight

Fields inherited from class ai.search.SearchEngineForIntCostFn

foundGoalNode, initialState

Fields inherited from class ai.search.SearchEngine

doInterrupt, doRepeatTest, searchLimit, searchStarted, traceStream, yieldFrequency

Constructor Summary

RBFSearcherForIntCostFn(S state, IntCostHeuristic<S> heuristic, int stackSize, long limit, SearchEngine.GraphType structure)
This constructor creates a new RBFSearcherForIntCostFn for the given initial state, heuristic, search stack size, search limit and search space type.

RBFSearcherForIntCostFn(S state, IntCostHeuristic<S> heuristic, long limit, SearchEngine.GraphType structure)
This constructor creates a new RBFSearcherForIntCostFn for the given initial state, heuristic, search limit and search space type.

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	setBreadthFirstTendency() This function causes an Exception to be thrown as this type of SearchEngine can only search in a depth-first manner.

Methods inherited from class ai.search.informed.BestFirstSearcherForIntCostFn

setDepthFirstTendency, setHeuristicWeight

Methods inherited from class ai.search.SearchEngineForIntCostFn

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 SearchEngineForIntCostFn.SearchNodeForIntCostFn<S extends SearchStateForIntCostFn>[] searchStack

the stack for unexplored (open) nodes

fValues

protected int[] fValues

the f-Values for the nodes in the stack

Constructor Detail

RBFSearcherForIntCostFn

public RBFSearcherForIntCostFn(S state,
                               IntCostHeuristic<S> heuristic,
                               long limit,
                               SearchEngine.GraphType structure)

This constructor creates a new RBFSearcherForIntCostFn for the given initial state, heuristic, search limit and search space type. Note that neither the given initial search state nor the given heuristic must 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

heuristic - the IntCostHeuristic function that guides the search

limit - the initial value for the search limit

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

RBFSearcherForIntCostFn

public RBFSearcherForIntCostFn(S state,
                               IntCostHeuristic<S> heuristic,
                               int stackSize,
                               long limit,
                               SearchEngine.GraphType structure)

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

The parameter stackSize should be set to the product of the maximal search depth that is expected and the branching factor. For example, if the search space has diameter of 31 and a branching factor of 4 (8-puzzle) a stack size of 31*4=124 will be sufficient.

Parameters:

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

heuristic - the IntCostHeuristic function that guides the search

stackSize - the size of the stack used by the search engine

limit - the initial value for the search limit

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

Method Detail

setBreadthFirstTendency

public void setBreadthFirstTendency()

This function causes an Exception to be thrown as this type of SearchEngine can only search in a depth-first manner.

Overrides:

setBreadthFirstTendency in class BestFirstSearcherForIntCostFn<S extends SearchStateForIntCostFn>

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 SearchEngineForIntCostFn.foundGoalState() will return true, the search will be continuable (continuable() usually will return true), and SearchEngineForIntCostFn.getGoalState() will return a goal state, not null
• the search limit has been reached: in this case SearchEngineForIntCostFn.foundGoalState() will return false, the search will not be continuable (continuable() will return false), and SearchEngineForIntCostFn.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: in this case SearchEngineForIntCostFn.foundGoalState() will return false, the search will not be continuable (continuable() will return false), and SearchEngineForIntCostFn.getGoalState() will return null

Specified by:

doSearch in class SearchEngine

continuable

public boolean continuable()

This function tests whether the search may be continued. For this type of search engine this will be true only before the search has been started by calling doSearch().

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