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. The update methods and the getSolutionCostPair() method of this class use synchronization for thread-safety. All other methods are non-blocking.

  • Constructor Summary

    Constructors
    Constructor
    Description
    ProgressTracker()
    Constructs a ProgressTracker.

  • Method Summary

    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 to stop.
    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.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • ProgressTracker

      public ProgressTracker()
      Constructs a ProgressTracker.

  • Method Details

    • 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 thread-safe. However, it uses synchronization for thread-safety, 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 nonblocking getCost() 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 thread-safe. However, it uses synchronization for thread-safety, 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 nonblocking getCostDouble() 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 thread-safe.
      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 thread-safe, and the solution and cost contained in the returned object are guaranteed to correspond with each other. However, it uses synchronization for thread-safety, so if all you need is the current cost, you should instead use the non-blocking getCost() or getCostDouble() methods. Likewise, if all you need is the solution, you should instead use the non-blocking getSolution() 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 floating-point valued cost, then the behavior of this method is undefined. Use the getCostDouble() 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 to stop.

    • 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.