ai.search
Class SearchEngineForIntCostFn<S extends SearchStateForIntCostFn>

java.lang.Object
  ai.search.SearchEngine
      ai.search.SearchEngineForIntCostFn<S>

Direct Known Subclasses:

BestFirstSearcherForIntCostFn, BidirBFSearcherForIntCostFn, BreadthFirstSearcherForIntCostFn, DepthFirstSearcherForIntCostFn, IDSearcherForIntCostFn, UniformCostSearcherForIntCostFn

public abstract class SearchEngineForIntCostFn<S extends SearchStateForIntCostFn>
extends SearchEngine

This class is a generic AI search engine that traverses a search space defined by an initial search state and a set of available actions.

What this class does provide is a number of administrative functions that are common to all search engines.

Author:

Gerhard Wickler

See Also:

IntCostAction, SearchStateForIntCostFn

Nested Class Summary

static class

SearchEngineForIntCostFn.SearchNodeForIntCostFn<S extends SearchStateForIntCostFn> A search node is a data structure created by a search engine to keep track of the portion of the search space explored so far.

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

SearchEngine.GraphType

Field Summary

protected SearchEngineForIntCostFn.SearchNodeForIntCostFn<S>	foundGoalNode the goal node that has been found or null when no such node has been discovered (yet)
protected S	initialState the initial state for the search; this value must be set by the constructor

Fields inherited from class ai.search.SearchEngine

doInterrupt, doRepeatTest, searchLimit, searchStarted, traceStream, yieldFrequency

Constructor Summary

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

Method Summary

boolean	foundGoalState() This function returns whether a goal state has been found.
S	getGoalState() This function returns the goal state that has been found if any.
S	getInitialState() This function returns the initial search state used for the current search.
int	getSolutionDepth() This function returns the depth of the found goal node in the generated search tree.
java.util.List<inf.util.Pair<IntCostAction,S>>	getSolutionPath() This function returns the complete path from the initial state to the goal state found.
int	getSolutionPathCost() This function returns the path cost of the path leading to the found goal state.

Methods inherited from class ai.search.SearchEngine

clone, continuable, doSearch, equals, getNrOfExploredStates, getNrOfGeneratedStates, getSearchLimit, hashCode, interrupt, printTrace, setSearchLimit, setTraceStream, setYieldFrequency, toString

Methods inherited from class java.lang.Object

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

Field Detail

initialState

protected S extends SearchStateForIntCostFn initialState

the initial state for the search; this value must be set by the constructor

foundGoalNode

protected SearchEngineForIntCostFn.SearchNodeForIntCostFn<S extends SearchStateForIntCostFn> foundGoalNode

the goal node that has been found or null when no such node has been discovered (yet)

Constructor Detail

SearchEngineForIntCostFn

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

This constructor creates a new SearchEngineForIntCostFn 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 SearchEngine.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

foundGoalState

public boolean foundGoalState()

This function returns whether a goal state has been found. Notice that a call to this function only makes sense after SearchEngine.doSearch() has been called at least once.

Specified by:

foundGoalState in class SearchEngine

Returns:

whether the search was successful and a goal state has been discovered

getSolutionDepth

public int getSolutionDepth()

This function returns the depth of the found goal node in the generated search tree.

Specified by:

getSolutionDepth in class SearchEngine

Returns:

the depth of the goal node

getInitialState

public S getInitialState()

This function returns the initial search state used for the current search.

Returns:

the initial SearchStateForIntCostFn

getGoalState

public S getGoalState()

This function returns the goal state that has been found if any. If no goal state has been found this function returns null.

Returns:

a SearchStateForIntCostFn that has been found and satisfies the goal test or null

getSolutionPath

public java.util.List<inf.util.Pair<IntCostAction,S>> getSolutionPath()

This function returns the complete path from the initial state to the goal state found. The List contains Pairs consisting of an IntCostAction and a SearchStateForIntCostFn each. The first Pair will contain the initial state and null as its action component. For all other elements the action in the Pair is applicable in the preceding Pair's state and leads to the state in the Pair. The state in the final pair will be a goal state.

Returns:

a List> containing the complete path from the initial state to a goal state including all intermediate states and actions representing the state transitions

getSolutionPathCost

public int getSolutionPathCost()

This function returns the path cost of the path leading to the found goal state.

Returns:

the accumulated cost of all the actions on the path from the initial state to the goal state