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

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

Direct Known Subclasses:

AStarSearcherForIntCostFn, GreedySearcherForIntCostFn, IDAStarSearcherForIntCostFn, MAStarSearcherForIntCostFn, RandomizedAStarSearcherForIntCostFn, RBFSearcherForIntCostFn

public abstract class BestFirstSearcherForIntCostFn<S extends SearchStateForIntCostFn>
extends SearchEngineForIntCostFn<S>

This class is a generic heuristic search engine that traverses a search space defined by an initial state and a set of available actions. The order in which nodes are expanded is determined (in part) by the heuristic.

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 boolean	dfTendency whether to apply depth-first search for states of equal f-value
protected IntCostHeuristic<S>	h the Heuristic to be used for the search
protected int	hweight the relative weight given to the heuristic; default is 1

Fields inherited from class ai.search.SearchEngineForIntCostFn

foundGoalNode, initialState

Fields inherited from class ai.search.SearchEngine

doInterrupt, doRepeatTest, searchLimit, searchStarted, traceStream, yieldFrequency

Constructor Summary

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

Method Summary

void	setBreadthFirstTendency() This function can be used to make this SearchEngine apply a breadth-first strategy for nodes of equal f-value.
void	setDepthFirstTendency() This function can be used to make this SearchEngine apply a depth-first strategy for nodes of equal f-value.
void	setHeuristicWeight(int weight) This function can be used to assign a specific weight to the heuristic when computing the f-value which determines the search order.

Methods inherited from class ai.search.SearchEngineForIntCostFn

foundGoalState, getGoalState, getInitialState, getSolutionDepth, getSolutionPath, getSolutionPathCost

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

h

protected IntCostHeuristic<S extends SearchStateForIntCostFn> h

the Heuristic to be used for the search

hweight

protected int hweight

the relative weight given to the heuristic; default is 1

dfTendency

protected boolean dfTendency

whether to apply depth-first search for states of equal f-value

Constructor Detail

BestFirstSearcherForIntCostFn

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

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

heuristic - the heuristic 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

Method Detail

setHeuristicWeight

public void setHeuristicWeight(int weight)

This function can be used to assign a specific weight to the heuristic when computing the f-value which determines the search order. Usually, this value should 1 or greater. Note that this is only relevant for some types of best-first search engine, not for all.

Parameters:

weight - the factor with which the h-value will be multiplied

setDepthFirstTendency

public void setDepthFirstTendency()

This function can be used to make this SearchEngine apply a depth-first strategy for nodes of equal f-value. This is the default strategy.

setBreadthFirstTendency

public void setBreadthFirstTendency()

This function can be used to make this SearchEngine apply a breadth-first strategy for nodes of equal f-value.