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

Class TSP

java.lang.Object
org.cicirello.search.problems.tsp.BaseTSP
org.cicirello.search.problems.tsp.TSP
All Implemented Interfaces:
Problem<Permutation>
Direct Known Subclasses:
TSP.Double, TSP.DoubleMatrix, TSP.Integer, TSP.IntegerMatrix
public abstract class TSP extends BaseTSP
This class and its nested classes implement the Traveling Salesperson Problem (TSP), such that cities are 2D points, and edge costs is the distance between them. The default distance is Euclidean distance, but any distance function can be configured by implementing the TSPEdgeDistance interface. The TSP class provides two inner classes where edge weights are computed as needed, one for edge costs that are floating-point valued (class TSP.Double), and one for integer cost edges (class TSP.Integer); and it also provides two inner classes where the edge weights are precomputed, one for edge costs that are floating-point valued (class TSP.DoubleMatrix), and one for integer cost edges (class TSP.IntegerMatrix). The nested classes with precomputed edge weights (TSP.DoubleMatrix and TSP.IntegerMatrix) may lead to faster runtimes for most search algorithms, but uses quadratic memory which may be prohibitive for TSP instances with a very large number of cities. Whereas the other two classes that compute each edge weight each time it is needed (TSP.Double and TSP.Integer), may be slower (by a constant factor) but only use linear memory, and are thus applicable to much larger TSP instances.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static final class 
    TSP.Double
    Cost function for the Traveling Salesperson Problem (TSP), where edge costs are floating-point valued.
    static final class 
    TSP.DoubleMatrix
    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.
    static final class 
    TSP.Integer
    Cost function for the Traveling Salesperson Problem (TSP), where edge costs are integer valued.
    static final class 
    TSP.IntegerMatrix
    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.

  • Method Summary

    Modifier and Type
    Method
    Description
    final double
    getX(int i)
    Gets the x coordinate of a city.
    final double
    getY(int i)
    Gets the y coordinate of a city.
    final int
    length()
    Gets the number of cities in the TSP instance.

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

    costAsDouble, getSolutionCostPair

  • Method Details

    • length

      public final int length()
      Gets the number of cities in the TSP instance.
      Specified by:
      length in class BaseTSP
      Returns:
      number of cities

    • getX

      public final double getX(int i)
      Gets the x coordinate of a city.
      Parameters:
      i - The city index.
      Returns:
      the x coordinate of city i.
      Throws:
      ArrayIndexOutOfBoundsException - if i < 0 or i ≥ length().

    • getY

      public final double getY(int i)
      Gets the y coordinate of a city.
      Parameters:
      i - The city index.
      Returns:
      the y coordinate of city i.
      Throws:
      ArrayIndexOutOfBoundsException - if i < 0 or i ≥ length().