
Orbital library  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object orbital.algorithm.template.GeneralSearch orbital.algorithm.template.GeneralBoundingSearch orbital.algorithm.template.BranchAndBound orbital.algorithm.template.ParallelBranchAndBound
public class ParallelBranchAndBound
Parallel branchandbound algorithm.
Visits the next nodes in parallel and bound by the best solution
known. Even though the implementation uses a stack of nodes, due
to the parallel nature this algorithm behaves much like BreadthFirstSearch
. However, the scheduling policy of the thread
scheduler may introduce a probabilistic behaviour in execution
speed.
Parallel algorithms profit much from multiprocessors, but their benefits are nevertheless not limited to those machines. Even singleprocessor systems can experience a speedup when using a parallel variant of a simple algorithm.
The speedup S(n) := T(1)/T(n) in execution time T(n) on an n processor system is in general in 1≤S(n)≤I(n)≤n, with I(n) := P(n)/T(n) being the parallel index of mean parallelization on an n processor system (P(n) := number of operations on n processors).
However, in rare cases superlinear speedups of S(n)>n can be observed due to synergy effects, even though they impossible from a theoretical perspective. In fact, they result from comparing slightly different(!) algorithms, or from more memory or larger caches. Yet, when they occur these advantages should be exploited.
ParallelBranchAndBound very often is such a case where superlinear speedups occur, because a parallel depthfirst search no longer is depthfirst in the large. In combination with the bounding, the synergetic effects result from the fact that the one thread's success may simplify another thread's job. By its sheer parallelity, the parallel depthfirst branchandbound more resembles breadthfirst search inspite of its implementation similarity with depthfirst search. And this explains why using ParallelBranchAndBound can result in a better performance even on singleprocessor systems.
BreadthFirstSearch
,
Serialized FormNested Class Summary 

Nested classes/interfaces inherited from class orbital.algorithm.template.GeneralSearch 

GeneralSearch.OptionIterator 
Nested classes/interfaces inherited from interface orbital.algorithm.template.HeuristicAlgorithm 

HeuristicAlgorithm.Configuration, HeuristicAlgorithm.PatternDatabaseHeuristic 
Nested classes/interfaces inherited from interface orbital.algorithm.template.EvaluativeAlgorithm 

EvaluativeAlgorithm.EvaluationComparator 
Constructor Summary  

ParallelBranchAndBound(Function heuristic,
double bound)

Method Summary  

Function 
complexity()
O(d) on parallel machines where d the solution depth. 
protected java.util.Iterator 
createTraversal(GeneralSearchProblem problem)
Define a traversal order by creating an iterator for the problem's state space. 
protected java.lang.Object 
search(java.util.Iterator nodes)
Run the general search algorithm scheme. 
protected java.lang.Object 
solveImpl(GeneralSearchProblem problem)
Implements the solution policy. 
Function 
spaceComplexity()
O(b^{d}) where b is the branching factor and d the solution depth. 
Methods inherited from class orbital.algorithm.template.BranchAndBound 

getEvaluation, getHeuristic, getMaxBound, isOptimal, processSolution, setHeuristic, setMaxBound, setMaxBound 
Methods inherited from class orbital.algorithm.template.GeneralBoundingSearch 

getBound, isContinuedWhenFound, isOutOfBounds, setBound, setBound, setContinuedWhenFound 
Methods inherited from class orbital.algorithm.template.GeneralSearch 

getProblem, solve 
Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Methods inherited from interface orbital.algorithm.template.AlgorithmicTemplate 

solve 
Constructor Detail 

public ParallelBranchAndBound(Function heuristic, double bound)
Method Detail 

public Function complexity()
complexity
in interface AlgorithmicTemplate
complexity
in class BranchAndBound
AlgorithmicTemplate.solve(AlgorithmicProblem)
public Function spaceComplexity()
spaceComplexity
in interface AlgorithmicTemplate
AlgorithmicTemplate.solve(AlgorithmicProblem)
protected java.lang.Object solveImpl(GeneralSearchProblem problem)
GeneralSearch
Like the default solution policies, this implementation will
GeneralSearch.createTraversal(GeneralSearchProblem)
.
GeneralSearch.search(Iterator)
to search through the state space in the traversal order.
solveImpl
in class BranchAndBound
GeneralSearch.search(Iterator)
.GeneralSearch.search(Iterator)
protected final java.util.Iterator createTraversal(GeneralSearchProblem problem)
GeneralSearch
Lays a linear order through the state space which the search can simply follow sequentially. Thus a traversal policy effectively reduces a search problem through a graph to a search problem through a linear sequence of states. Of course, the mere notion of a traversal policy does not yet solve the task of finding a good order of states, but only encapsulate it. Complete search algorithms result from traversal policies that have a linear sequence through the whole state space.
problem
 the problem whose state space to create a traversal iterator for.
GeneralSearch.OptionIterator
protected java.lang.Object search(java.util.Iterator nodes)
GeneralBoundingSearch
This method only needs to be overwritten to provide a completely different search scheme. Usually, the default search algorithm scheme is sufficient.
search
in class GeneralBoundingSearch
nodes
 is the iterator over the nodes to visit (sometimes called open set)
which determines the traversal order.

Orbital library 1.3.0: 11 Apr 2009 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 