Module org.cicirello.chips_n_salsa
Package org.cicirello.search.problems.tsp

Class TSP.Double

java.lang.Object
org.cicirello.search.problems.tsp.BaseTSP
org.cicirello.search.problems.tsp.TSP
org.cicirello.search.problems.tsp.TSP.Double
All Implemented Interfaces:
OptimizationProblem<Permutation>, Problem<Permutation>
Enclosing class:
TSP
public static final class TSP.Double extends TSP implements OptimizationProblem<Permutation>
Cost function for the Traveling Salesperson Problem (TSP), where edge costs are floating-point valued. This implementation only requires linear memory, but must recompute an edge cost every time it is needed. If your instance of the TSP is small enough to afford quadratic memory, then you may prefer the TSP.DoubleMatrix class which precomputes all edge costs between all pairs of cities.

  • Nested Class Summary

    Nested classes/interfaces inherited from class org.cicirello.search.problems.tsp.TSP

    TSP.Double, TSP.DoubleMatrix, TSP.Integer, TSP.IntegerMatrix

  • Constructor Summary

    Constructors
    Constructor
    Description
    Double(double[] x, double[] y)
    Constructs a TSP instance with city locations specified by arrays of x and y coordinates.
    Double(double[] x, double[] y, TSPEdgeDistance distance)
    Constructs a TSP instance with city locations specified by arrays of x and y coordinates.
    Double(int n, double w)
    Constructs a random TSP instance with cities randomly distributed within a square region.
    Double(int n, double w, long seed)
    Constructs a random TSP instance with cities randomly distributed within a square region.
    Double(int n, double w, TSPEdgeDistance distance)
    Constructs a random TSP instance with cities randomly distributed within a square region.
    Double(int n, double w, TSPEdgeDistance distance, long seed)
    Constructs a random TSP instance with cities randomly distributed within a square region.

  • Method Summary

    Modifier and Type
    Method
    Description
    double
    cost(Permutation candidate)
    Computes the cost of a candidate solution to the problem instance.
    double
    minCost()
    A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution.
    double
    value(Permutation candidate)
    Computes the value of the candidate solution within the usual constraints and interpretation of the problem.

    Methods inherited from class org.cicirello.search.problems.tsp.TSP

    getX, getY, length

    Methods inherited from class java.lang.Object

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

    Methods inherited from interface org.cicirello.search.problems.OptimizationProblem

    costAsDouble, getSolutionCostPair, isMinCost

  • Constructor Details

    • Double

      public Double(int n, double w)
      Constructs a random TSP instance with cities randomly distributed within a square region. The edge cost of a pair of cities is the Euclidean distance between them.
      Parameters:
      n - The number of cities.
      w - The width (and height) of a square region containing the cities.
      Throws:
      IllegalArgumentException - if n < 2.
      IllegalArgumentException - if w ≤ 0.0.

    • Double

      public Double(int n, double w, TSPEdgeDistance distance)
      Constructs a random TSP instance with cities randomly distributed within a square region.
      Parameters:
      n - The number of cities.
      w - The width (and height) of a square region containing the cities.
      distance - The distance function to use for the edge costs.
      Throws:
      IllegalArgumentException - if n < 2.
      IllegalArgumentException - if w ≤ 0.0.

    • Double

      public Double(int n, double w, long seed)
      Constructs a random TSP instance with cities randomly distributed within a square region. The edge cost of a pair of cities is the Euclidean distance between them.
      Parameters:
      n - The number of cities.
      w - The width (and height) of a square region containing the cities.
      seed - The seed for the random number generator to enable reproducing the same instance for experiment reproducibility.
      Throws:
      IllegalArgumentException - if n < 2.
      IllegalArgumentException - if w ≤ 0.0.

    • Double

      public Double(int n, double w, TSPEdgeDistance distance, long seed)
      Constructs a random TSP instance with cities randomly distributed within a square region.
      Parameters:
      n - The number of cities.
      w - The width (and height) of a square region containing the cities.
      distance - The distance function to use for the edge costs.
      seed - The seed for the random number generator to enable reproducing the same instance for experiment reproducibility.
      Throws:
      IllegalArgumentException - if n < 2.
      IllegalArgumentException - if w ≤ 0.0.

    • Double

      public Double(double[] x, double[] y)
      Constructs a TSP instance with city locations specified by arrays of x and y coordinates. The edge cost of a pair of cities is the Euclidean distance between them.
      Parameters:
      x - Array of x coordinates.
      y - Array of y coordinates.
      Throws:
      IllegalArgumentException - if x.length is not equal to y.length.
      IllegalArgumentException - if the length of the arrays is less than 2.

    • Double

      public Double(double[] x, double[] y, TSPEdgeDistance distance)
      Constructs a TSP instance with city locations specified by arrays of x and y coordinates.
      Parameters:
      x - Array of x coordinates.
      y - Array of y coordinates.
      distance - The distance function to use for the edge costs.
      Throws:
      IllegalArgumentException - if x.length is not equal to y.length.
      IllegalArgumentException - if the length of the arrays is less than 2.

  • Method Details

    • cost

      public double cost(Permutation candidate)
      Description copied from interface: OptimizationProblem
      Computes the cost of a candidate solution to the problem instance. The lower the cost, the more optimal the candidate solution.
      Specified by:
      cost in interface OptimizationProblem<Permutation>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The cost of the candidate solution. Lower cost means better solution.

    • value

      public double value(Permutation candidate)
      Description copied from interface: OptimizationProblem
      Computes the value of the candidate solution within the usual constraints and interpretation of the problem.
      Specified by:
      value in interface OptimizationProblem<Permutation>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The actual optimization value of the candidate solution.

    • minCost

      public double minCost()
      Description copied from interface: OptimizationProblem
      A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution. The default implementation returns Double.NEGATIVE_INFINITY.
      Specified by:
      minCost in interface OptimizationProblem<Permutation>
      Returns:
      A lower bound on the minimum theoretical cost of the problem instance.