ai.search.uninformed
Class BidirBFSearcherForIntCostFn<S extends SearchStateForIntCostFn>

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

public class BidirBFSearcherForIntCostFn<S extends SearchStateForIntCostFn>
extends SearchEngineForIntCostFn<S>

This class represents a search engine that traverses a search space bi-directionally in breadth first order from a given initial state and a given goal state. The initial state, the goal state, the search limit, and the type of search space must be given to this search engine at construction time. The search limit may be increased later using SearchEngine.setSearchLimit(long).

The search must be started using the function doSearch(). Successors of the initial state and predecessors of the goal state state will then be explored in the order of their depth in the search tree. The search will halt when the two search fringes meet, i.e. when a path from the initial state to the goal state has been found. This path can then be inspected using the appropriate functions described in the SearchEngineForIntCostFn class.

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

      SearchEngineForIntCostFn s = new BidirBFSearcherForIntCostFn(
              initialState, goalState, 1000, GRAPH);
      s.doSearch();
      if (s.foundGoalState()) { ... }
 

To continue the search call doSearch() again and the search will be continued as far as possible. This may result in the discovery of alternative paths to the goal state.

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 java.util.Map<S,SearchEngineForIntCostFn.SearchNodeForIntCostFn<S>>	foundStatesBwd the table of all states generated this far for the test for repeated states for the backward search
protected java.util.Map<S,SearchEngineForIntCostFn.SearchNodeForIntCostFn<S>>	foundStatesFwd the table of all states generated this far for the test for repeated states for the forward search
protected S	goalState the goal state from which the backward search starts
protected java.util.List<SearchEngineForIntCostFn.SearchNodeForIntCostFn<S>>	searchQueueBwd the search queue for explored (closed) and unexplored (open) nodes for the backward search
protected java.util.List<SearchEngineForIntCostFn.SearchNodeForIntCostFn<S>>	searchQueueFwd the search queue for explored (closed) and unexplored (open) nodes for the forward search

Fields inherited from class ai.search.SearchEngineForIntCostFn

foundGoalNode, initialState

Fields inherited from class ai.search.SearchEngine

doInterrupt, doRepeatTest, searchLimit, searchStarted, traceStream, yieldFrequency

Constructor Summary

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

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.
int	getSolutionDepth() This function returns the depth of the goal node which is the number of steps in the found path leading to it.
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 goal state.

Methods inherited from class ai.search.SearchEngineForIntCostFn

foundGoalState, getGoalState, getInitialState

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

searchQueueFwd

protected java.util.List<SearchEngineForIntCostFn.SearchNodeForIntCostFn<S extends SearchStateForIntCostFn>> searchQueueFwd

the search queue for explored (closed) and unexplored (open) nodes for the forward search

searchQueueBwd

protected java.util.List<SearchEngineForIntCostFn.SearchNodeForIntCostFn<S extends SearchStateForIntCostFn>> searchQueueBwd

the search queue for explored (closed) and unexplored (open) nodes for the backward search

foundStatesFwd

protected java.util.Map<S extends SearchStateForIntCostFn,SearchEngineForIntCostFn.SearchNodeForIntCostFn<S extends SearchStateForIntCostFn>> foundStatesFwd

the table of all states generated this far for the test for repeated states for the forward search

foundStatesBwd

protected java.util.Map<S extends SearchStateForIntCostFn,SearchEngineForIntCostFn.SearchNodeForIntCostFn<S extends SearchStateForIntCostFn>> foundStatesBwd

the table of all states generated this far for the test for repeated states for the backward search

goalState

protected S extends SearchStateForIntCostFn goalState

the goal state from which the backward search starts

Constructor Detail

BidirBFSearcherForIntCostFn

public BidirBFSearcherForIntCostFn(S iState,
                                   S gState,
                                   long limit,
                                   SearchEngine.GraphType structure)

This constructor creates a new BidirBFSearcherForIntCostFn for the given initial state, goal state, search limit, and type of search space. Note that the given initial and goal state must not be null. The search does not start immediately but waits for the function doSearch() to be called.

Parameters:

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

gState - the goal 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

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. Usually this is the case if there are more search states to be explored (in both queues) and the search limit has not yet been exceeded.

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

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.

Overrides:

getSolutionPath in class SearchEngineForIntCostFn<S extends SearchStateForIntCostFn>

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

getSolutionDepth

public int getSolutionDepth()

This function returns the depth of the goal node which is the number of steps in the found path leading to it.

Overrides:

getSolutionDepth in class SearchEngineForIntCostFn<S extends SearchStateForIntCostFn>

Returns:

the depth of the goal node

getSolutionPathCost

public int getSolutionPathCost()

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

Overrides:

getSolutionPathCost in class SearchEngineForIntCostFn<S extends SearchStateForIntCostFn>

Returns:

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