Class TSP.IntegerMatrix

java.lang.Object
org.cicirello.search.problems.tsp.BaseTSP
org.cicirello.search.problems.tsp.TSP
org.cicirello.search.problems.tsp.TSP.IntegerMatrix
All Implemented Interfaces:
IntegerCostOptimizationProblem<Permutation>, Problem<Permutation>
Enclosing class:
TSP
public static final class TSP.IntegerMatrix extends TSP implements IntegerCostOptimizationProblem<Permutation>
Cost function for the Traveling Salesperson Problem (TSP), where edge costs are integer valued, and where all edge costs between pairs of cities are precomputed. This implementation requires quadratic memory, and may be prohibitive for large instances, in which case you may prefer to use the TSP.Integer class, that only requires linear memory but recomputes an edge cost every time it is needed.

  • Constructor Details

    • IntegerMatrix

      public IntegerMatrix(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 rounded to the nearest integer.
      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.

    • IntegerMatrix

      public IntegerMatrix(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.

    • IntegerMatrix

      public IntegerMatrix(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 rounded to the nearest integer.
      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.

    • IntegerMatrix

      public IntegerMatrix(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.

    • IntegerMatrix

      public IntegerMatrix(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 rounded to the nearest integer.
      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.

    • IntegerMatrix

      public IntegerMatrix(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 int cost(Permutation candidate)
      Description copied from interface: IntegerCostOptimizationProblem
      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 IntegerCostOptimizationProblem<Permutation>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The cost of the candidate solution. Lower cost means better solution.

    • value

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

    • minCost

      public int minCost()
      Description copied from interface: IntegerCostOptimizationProblem
      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 Integer.MIN_VALUE.
      Specified by:
      minCost in interface IntegerCostOptimizationProblem<Permutation>
      Returns:
      A lower bound on the minimum theoretical cost of the problem instance.