java.lang.Object |
↳ |
es.usc.citius.hipster.algorithm.Algorithm<A, S, N extends es.usc.citius.hipster.model.Node<A, S, N>> |
|
↳ |
es.usc.citius.hipster.algorithm.BellmanFord<A, S, C extends java.lang.Comparable<C>, N extends es.usc.citius.hipster.model.CostNode<A, S, C, N>> |
Class Overview
Optimized implementation of the Bellman-Ford algorithm. The main difference with the standard version
of Bellman-Ford is that this implementation does not relax all edges at each iteration. This implies that
the first time the goal state is reached, the cost may not be the optimal one. The optimal cost is only guaranteed
when the queue is empty (when bellmanFordIt.hasNext() == false).
Original paper:
Bellman, R.
"On a routing problem".
Quarterly of Applied Mathematics (1958) 16: 87–90.
Summary
[Expand]
Inherited Methods |
From class
es.usc.citius.hipster.algorithm.Algorithm
static
<A, N extends Node<A, ?, N>>
List<A>
|
recoverActionPath(N node)
Returns a path of the actions applied from the initial state
to the state of the provided node ( state() ).
|
static
<S, N extends Node<?, S, N>>
List<S>
|
recoverStatePath(N node)
Returns a path with all the states of the path.
|
SearchResult
|
search(S goalState)
Run the algorithm until the goal is found or no more states are
available.
|
SearchResult
|
search(Predicate<N> condition)
Executes the search algorithm until the predicate condition is
satisfied or there are no more nodes to explore.
|
void
|
search(SearchListener<N> listener)
Executes the search algorithm and invokes the method
handle(Object) passing the current
explored node to the listener.
|
|
From class
java.lang.Object
Object
|
clone()
|
boolean
|
equals(Object arg0)
|
void
|
finalize()
|
final
Class<?>
|
getClass()
|
int
|
hashCode()
|
final
void
|
notify()
|
final
void
|
notifyAll()
|
String
|
toString()
|
final
void
|
wait()
|
final
void
|
wait(long arg0, int arg1)
|
final
void
|
wait(long arg0)
|
|
From interface
java.lang.Iterable
abstract
Iterator<T>
|
iterator()
|
|
Fields
protected
boolean
checkNegativeCycles
protected
N extends CostNode<A, S, C extends Comparable<C>, N>
initialNode
Public Constructors
public
BellmanFord
(N initialNode, NodeExpander<A, S, N> nodeExpander)
Public Methods
public
N
getInitialNode
()
public
boolean
isCheckNegativeCycles
()
Executes the search algorithm until the predicate condition is
satisfied or there are no more nodes to explore.
Parameters
condition |
predicate with the boolean condition. |
public
void
setCheckNegativeCycles
(boolean checkNegativeCycles)
public
void
setInitialNode
(N initialNode)
public
void
setNodeExpander
(NodeExpander<A, S, N> nodeExpander)