ai.search
Class SearchEngineForDoubleCostFn<S extends SearchStateForDoubleCostFn>

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

Direct Known Subclasses:

BidirBFSearcherForDoubleCostFn, BreadthFirstSearcherForDoubleCostFn, DepthFirstSearcherForDoubleCostFn, IDSearcherForDoubleCostFn, UniformCostSearcherForDoubleCostFn

public abstract class SearchEngineForDoubleCostFn<S extends SearchStateForDoubleCostFn>
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:

DoubleCostAction, SearchStateForDoubleCostFn

Nested Class Summary

protected static class

SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S extends SearchStateForDoubleCostFn> 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 SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<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

SearchEngineForDoubleCostFn(S state, long limit, SearchEngine.GraphType structure)
This constructor creates a new SearchEngineForDoubleCostFn 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<DoubleCostAction,S>>	getSolutionPath() This function returns the complete path from the initial state to the goal state found.
double	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 SearchStateForDoubleCostFn initialState

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

foundGoalNode

protected SearchEngineForDoubleCostFn.SearchNodeForDoubleCostFn<S extends SearchStateForDoubleCostFn> foundGoalNode

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

Constructor Detail

SearchEngineForDoubleCostFn

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

This constructor creates a new SearchEngineForDoubleCostFn 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 SearchStateForDoubleCostFn

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 SearchStateForDoubleCostFn that has been found and satisfies the goal test or null

getSolutionPath

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

This function returns the complete path from the initial state to the goal state found. The List contains Pairs consisting of a DoubleCostAction and a SearchStateForDoubleCostFn 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 double 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