Class TSP.DoubleMatrix

  • All Implemented Interfaces:
    OptimizationProblem<Permutation>, Problem<Permutation>
    Enclosing class:
    TSP

    public static final class TSP.DoubleMatrix
    extends TSP
    implements OptimizationProblem<Permutation>

    Cost function for the Traveling Salesperson Problem (TSP), where edge costs are floating-point 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.Double class, that only requires linear memory but recomputes an edge cost every time it is needed.

    • Constructor Detail

      • DoubleMatrix

        public DoubleMatrix​(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.
      • DoubleMatrix

        public DoubleMatrix​(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.
      • DoubleMatrix

        public DoubleMatrix​(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.
      • DoubleMatrix

        public DoubleMatrix​(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.
    • Method Detail

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