ai.search
Class SearchEngine

java.lang.Object
  ai.search.SearchEngine

Direct Known Subclasses:

SearchEngineForDoubleCostFn, SearchEngineForIntCostFn

public abstract class SearchEngine
extends java.lang.Object

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 mainly distinguishes different search engines is the order in which the search states that constitute the search space are explored. An inheriting class must specify this search strategy. Thus, the most important function of this class that needs to be overridden by an inheriting class is doSearch(), the function that actually explores the search space according to some strategy.

Author:

Gerhard Wickler

Nested Class Summary

static class

SearchEngine.GraphType

Field Summary

protected boolean	doInterrupt flag to be set if doSearch is to be interrupted
protected boolean	doRepeatTest indicates whether the test for repeated states should take place
protected long	searchLimit the maximum number of search nodes to be generated
protected boolean	searchStarted indicates whether the search has been started
protected java.io.OutputStream	traceStream the stream to which trace output should be written or null, the default value, for no tracing
protected int	yieldFrequency the search engine will call yield() every so many explored nodes; the default value is Integer.MAX_VALUE

Constructor Summary

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

Method Summary

protected java.lang.Object	clone() This class does not support cloning and an exception will be thrown if this method is called.
abstract boolean	continuable() This function tests whether the search may be continued.
abstract void	doSearch() This function must be called to start or continue the search.
boolean	equals(java.lang.Object obj) This class does not support equality testing and an exception will be thrown if this method is called.
abstract boolean	foundGoalState() This function returns whether a goal state has been found.
abstract long	getNrOfExploredStates() This function returns the number of states that have been explored during this search.
abstract long	getNrOfGeneratedStates() This function returns the number of states that have been generated during this search.
long	getSearchLimit() This function returns the current search limit, that is, the maximal number of search states to be generated.
abstract int	getSolutionDepth() This function returns the depth of the found goal node in the generated search tree.
int	hashCode() This class does not support hashing and an exception will be thrown if this method is called.
void	interrupt() This function sets the interrupt flag for this SearchEngine.
void	printTrace(java.lang.String msg) This function must be called to print out tracing messages.
void	setSearchLimit(long limit) This function can be used to set a new limit for the number of search states that are to be generated.
void	setTraceStream(java.io.OutputStream stream) This function can be used to activate tracing of the search activity.
void	setYieldFrequency(int frequency) This function can be used to set a new yield frequency.
java.lang.String	toString() This class does not support a printable representation and an exception will be thrown if this method is called.

Methods inherited from class java.lang.Object

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

Field Detail

traceStream

protected java.io.OutputStream traceStream

the stream to which trace output should be written or null, the default value, for no tracing

searchStarted

protected boolean searchStarted

indicates whether the search has been started

doRepeatTest

protected boolean doRepeatTest

indicates whether the test for repeated states should take place

searchLimit

protected long searchLimit

the maximum number of search nodes to be generated

yieldFrequency

protected int yieldFrequency

the search engine will call yield() every so many explored nodes; the default value is Integer.MAX_VALUE

doInterrupt

protected boolean doInterrupt

flag to be set if doSearch is to be interrupted

Constructor Detail

SearchEngine

public SearchEngine(long limit,
                    SearchEngine.GraphType structure)

This constructor creates a new SearchEngine for the given search limit, and type of search space. The search does not start immediately but waits for the function doSearch() to be called.

Parameters:

limit - the initial value for the search limit

structure - TREE or GRAPH, depending on what is to be be searched

Method Detail

clone

protected java.lang.Object clone()
                          throws java.lang.CloneNotSupportedException

This class does not support cloning and an exception will be thrown if this method is called.

Overrides:

clone in class java.lang.Object

Returns:

nothing

Throws:

java.lang.CloneNotSupportedException - will be thrown

doSearch

public abstract 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 foundGoalState() will return true
• the search limit has been reached: in this case foundGoalState() will return false, the search cannot be continued (continuable() will return false); to make the search continuable the search limit has to be increased using setSearchLimit(long)
• the search space has been exhausted: in this case foundGoalState() will return false, the search will not be continuable (continuable() will return false)

foundGoalState

public abstract boolean foundGoalState()

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

Returns:

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

getSolutionDepth

public abstract int getSolutionDepth()

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

Returns:

the depth of the goal node

continuable

public abstract 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 and the search limit has not yet been exceeded.

Returns:

true if and only if there are more search states that can be explored

getNrOfExploredStates

public abstract 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.

Returns:

the number of nodes that have been closed during this search

getNrOfGeneratedStates

public abstract 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.

Returns:

the number of states that have been generated during this search

setSearchLimit

public void setSearchLimit(long limit)

This function can be used to set a new limit for the number of search states that are to be generated. When a new search limit is set with this function, subsequent calls to doSearch() continue the search as if this had been the original limit.

Parameters:

limit - the new search limit value

getSearchLimit

public long getSearchLimit()

This function returns the current search limit, that is, the maximal number of search states to be generated.

Returns:

the currently used search limit

setTraceStream

public void setTraceStream(java.io.OutputStream stream)

This function can be used to activate tracing of the search activity. Setting the trace stream to null switches off tracing completely. Otherwise a trace is written to the given stream.

Parameters:

stream - the OutputStream to which the trace should be written or null for no tracing

printTrace

public void printTrace(java.lang.String msg)

This function must be called to print out tracing messages. Note that this function does not test whether tracing has been switched off, i.e. whether traceStream==null.

Parameters:

msg - the message to be printed to the trace stream

setYieldFrequency

public void setYieldFrequency(int frequency)

This function can be used to set a new yield frequency. It should only be used if there are indeed multiple threads running. The given value should depend on the time it takes to generate the successors of a state; the longer this time the higher the yield frequency should be.

Parameters:

frequency - the new frequency with which this search thread will yield control explicitly

interrupt

public void interrupt()

This function sets the interrupt flag for this SearchEngine. The implementation of doSearch() is expected to interrupt its search and return control to the calling Thread when this flag has been set.

equals

public boolean equals(java.lang.Object obj)
               throws java.lang.UnsupportedOperationException

This class does not support equality testing and an exception will be thrown if this method is called.

Overrides:

equals in class java.lang.Object

Parameters:

obj - the object this should be compared to

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - will be thrown

hashCode

public int hashCode()
             throws java.lang.UnsupportedOperationException

This class does not support hashing and an exception will be thrown if this method is called.

Overrides:

hashCode in class java.lang.Object

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - will be thrown

toString

public java.lang.String toString()
                          throws java.lang.UnsupportedOperationException

This class does not support a printable representation and an exception will be thrown if this method is called.

Overrides:

toString in class java.lang.Object

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - will be thrown