org.browsecode.helpers.aisearch
Class AStar<N>

java.lang.Object
  org.browsecode.helpers.aisearch.AStar<N>

All Implemented Interfaces:

java.lang.Runnable, AISearch<N>

public abstract class AStar<N>
extends java.lang.Object
implements AISearch<N>, java.lang.Runnable

Field Summary

static boolean

debug

Constructor Summary

AStar()

AStar(AISearchDomain<N> searchDomain)

Method Summary

protected void	doneWithRun() Override this to know when the run stops.
int	getNumberOfThreads()
protected AISearchDomain<N>	getSearchDomain()
int	getSleepInEachMultiThreadLoop()
void	run() Call this to start A-Star searching.
void	setNumberOfThreads(int numThreads) Set the number of threads for A-Star to use.
void	setSleepInEachMultiThreadLoop(int sleepInEachMultiThreadLoop) This is the number of milliseconds of sleep time between checking up on threads (only applies if you setNumberOfThreads(>1)).
protected void	startRun() Override this to know when the run starts.
protected boolean	stopNow() Subclasses may override this and set a point to stop, i.e. when we have a good enough solution, a certain number of solutions, etc.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

debug

public static final boolean debug

See Also:

Constant Field Values

Constructor Detail

AStar

public AStar()

AStar

public AStar(AISearchDomain<N> searchDomain)

Method Detail

getSearchDomain

protected AISearchDomain<N> getSearchDomain()

setNumberOfThreads

public void setNumberOfThreads(int numThreads)

Set the number of threads for A-Star to use. A-Star will automatically manage these threads and keep them at a high utilization. You may want to multi-thread A-Star if: (a) You have multiple processors (or hyperthreading on a pentium, which is not much faster) (b) Your processing has something that is slower than the processor -- i.e. if you have to wait for network tests, file IO, multiple threads may be a speedup because the processor would not fully utilized during each loop of A-Star. In this case, multiple threads could dramatically improve the speed. There are some times when you DON'T want to use multiple threads -- if you have only one processor, and it's processor intensive, and if it sometimes stops in the middle of the algoritm (i.e. you've made stopNow() return true because it ran out of time), having multiple threads can reduce efficiency and end up not getting the best answer in a limited time. A-Star should (and according to our tests, does) return the same results even in multiple threads -- that's one huge benefit of A-Star over other algorithms.

getNumberOfThreads

public int getNumberOfThreads()

startRun

protected void startRun()

Override this to know when the run starts.

doneWithRun

protected void doneWithRun()

Override this to know when the run stops.

stopNow

protected boolean stopNow()

Subclasses may override this and set a point to stop, i.e. when we have a good enough solution, a certain number of solutions, etc.

Returns:

getSleepInEachMultiThreadLoop

public int getSleepInEachMultiThreadLoop()

setSleepInEachMultiThreadLoop

public void setSleepInEachMultiThreadLoop(int sleepInEachMultiThreadLoop)

This is the number of milliseconds of sleep time between checking up on threads (only applies if you setNumberOfThreads(>1)). You may want to fine tune this depending upon your algorithm. If you know how long a loop takes to process, roughly, you want to set this number to HIGHER than that loop time. The higher the time to sleep, the more time each thread has to run, but there will be more dead threads sitting idle. There is always one more thread than getNumberOfThreads() -- the thread that checks up on those to see if they've died, the thread you sent in. That thread should be sleeping most of the time, but coming out often enough to check that it doesn't waste any processors. OPTION FOR SPEED: Another implementation of run() and the AStarSingleSearch.run() could eliminate this extra thread, but it's unclear that it would save any time.

Parameters:

sleepInEachMultiThreadLoop -

run

public void run()

Call this to start A-Star searching. If you want this to use multiple threads, setNumberOfThreads() before this option -- do NOT run this multiple times simultaneously. This will not return until the search is done.

Specified by:

run in interface java.lang.Runnable