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

java.lang.Object
  extended by ai.search.SearchEngine
      extended by ai.search.SearchEngineForIntCostFn<S>
          extended by 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.