Module org.cicirello.chips_n_salsa
Package org.cicirello.search
Class ProgressTracker<T extends Copyable<T>>
 java.lang.Object

 org.cicirello.search.ProgressTracker<T>

 Type Parameters:
T
 The type of object the search is optimizing.
public final class ProgressTracker<T extends Copyable<T>> extends Object
This class is used to track search algorithm progress, and supports multithreaded search algorithms. For a multithreaded search algorithm, all search threads should share a single instance. Theupdate
methods and thegetSolutionCostPair()
method of this class use synchronization for threadsafety. All other methods are nonblocking.


Constructor Summary
Constructors Constructor Description ProgressTracker()
Constructs a ProgressTracker.

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
containsIntCost()
Checks whether the cost of the solution contained in this ProgressTracker is integer valued.boolean
didFindBest()
Check whether the solution contained in the ProgressTracker has been marked as the best possible solution.long
elapsed()
Gets the amount of time (nanoseconds precision) that elapsed between when this ProgressTracker was constructed and the most recent successful update of the best solution contained within the tracker.int
getCost()
Gets the cost of the current best solution stored in the ProgressTracker.double
getCostDouble()
Gets the cost of the current best solution stored in the ProgressTracker.T
getSolution()
Gets the current best solution stored in the ProgressTracker.SolutionCostPair<T>
getSolutionCostPair()
Gets the current best solution and its corresponding cost from the ProgressTracker.boolean
isStopped()
Checks whether a flag is set indicating that all searches sharing this ProgressTracker should stop.void
start()
Resets the stop flag to false, essentially undoing a previous call tostop
.void
stop()
Set a flag that indicates that all searches sharing this ProgressTracker should stop their search when able to (e.g., such as at the end of the next iteration.double
update(double cost, T solution, boolean isKnownOptimal)
Updates the best solution contained in this progress tracker.int
update(int cost, T solution, boolean isKnownOptimal)
Updates the best solution contained in this progress tracker.boolean
update(SolutionCostPair<T> pair)
Updates the best solution contained in this progress tracker.



Method Detail

update
public int update(int cost, T solution, boolean isKnownOptimal)
Updates the best solution contained in this progress tracker. The update takes place only if the new solution has lower cost than the current best cost solution stored in the progress tracker. This method is threadsafe. However, it uses synchronization for threadsafety, so it is strongly suggested that in multithreaded search implementations that you reserve calls to this method for when the search believes it has likely found a better solution than all currently running threads. Although in theory the functionality of this class is such that it can be used as the sole means of a search algorithm keeping track of the best found solution. If multiple parallel runs attempt to share this object for that purpose, significant blocking may occur. You may consider using the nonblockinggetCost()
method first. Parameters:
cost
 The cost of the solution.solution
 The new solution.isKnownOptimal
 Pass true if this solution is known to be the optimal such as if it is equal to a lower bound for the problem, and otherwise pass false. Returns:
 The cost of the best solution found. This may or may not be equal to the cost passed as a parameter. If the returned value is less than cost, then that means the best solution was previously updated by this or another thread.

update
public double update(double cost, T solution, boolean isKnownOptimal)
Updates the best solution contained in this progress tracker. The update takes place only if the new solution has lower cost than the current best cost solution stored in the progress tracker. This method is threadsafe. However, it uses synchronization for threadsafety, so it is strongly suggested that in multithreaded search implementations that you reserve calls to this method for when the search believes it has likely found a better solution than all currently running threads. Although in theory the functionality of this class is such that it can be used as the sole means of a search algorithm keeping track of the best found solution. If multiple parallel runs attempt to share this object for that purpose, significant blocking may occur. You may consider using the nonblockinggetCostDouble()
method first. Parameters:
cost
 The cost of the solution.solution
 The new solution.isKnownOptimal
 Pass true if this solution is known to be the optimal such as if it is equal to a lower bound for the problem, and otherwise pass false. Returns:
 The cost of the best solution found. This may or may not be equal to the cost passed as a parameter. If the returned value is less than cost, then that means the best solution was previously updated by this or another thread.

update
public boolean update(SolutionCostPair<T> pair)
Updates the best solution contained in this progress tracker. The update takes place only if the new solution has lower cost than the current best cost solution stored in the progress tracker. This method is threadsafe. Parameters:
pair
 A solution cost pair. Returns:
 true If the cost of the solution in the ProgressTracker is that of this pair at the time that this method returns, which will be the case if this pair contains a new best solution or a solution with cost equal to that contained in the ProgressTracker. It otherwise returns false.

getSolutionCostPair
public SolutionCostPair<T> getSolutionCostPair()
Gets the current best solution and its corresponding cost from the ProgressTracker. This method is threadsafe, and the solution and cost contained in the returned object are guaranteed to correspond with each other. However, it uses synchronization for threadsafety, so if all you need is the current cost, you should instead use the nonblockinggetCost()
orgetCostDouble()
methods. Likewise, if all you need is the solution, you should instead use the nonblockinggetSolution()
method. Returns:
 current best solution and its corresponding cost

getCost
public int getCost()
Gets the cost of the current best solution stored in the ProgressTracker. If update(double, T) was used to set a floatingpoint valued cost, then the behavior of this method is undefined. Use thegetCostDouble()
method instead. Returns:
 the cost of the current best solution

getCostDouble
public double getCostDouble()
Gets the cost of the current best solution stored in the ProgressTracker. Returns:
 the cost of the current best solution

getSolution
public T getSolution()
Gets the current best solution stored in the ProgressTracker. Returns:
 the current best solution

elapsed
public long elapsed()
Gets the amount of time (nanoseconds precision) that elapsed between when this ProgressTracker was constructed and the most recent successful update of the best solution contained within the tracker. Returns:
 time (in nanoseconds) between ProgressTracker construction and most recent recording of best solution.

didFindBest
public boolean didFindBest()
Check whether the solution contained in the ProgressTracker has been marked as the best possible solution. Returns:
 true if the ProgressTracker contains the best possible solution.

stop
public void stop()
Set a flag that indicates that all searches sharing this ProgressTracker should stop their search when able to (e.g., such as at the end of the next iteration.

start
public void start()
Resets the stop flag to false, essentially undoing a previous call tostop
.

isStopped
public boolean isStopped()
Checks whether a flag is set indicating that all searches sharing this ProgressTracker should stop. Returns:
 true if the searches sharing this ProgressTracker should stop.

containsIntCost
public boolean containsIntCost()
Checks whether the cost of the solution contained in this ProgressTracker is integer valued. Returns:
 true if the most recently set solution has integer valued cost, and false
otherwise. If this method returns false, then the behavior of the
getCost()
method is undefined.

