Class TSP

  • Direct Known Subclasses:
    TSP.Double, TSP.DoubleMatrix, TSP.Integer, TSP.IntegerMatrix

    public abstract class TSP
    extends Object

    This class and its nested classes implement the Traveling Salesperson Problem (TSP). It 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 class  TSP.Double
      Cost function for the Traveling Salesperson Problem (TSP), where edge costs are floating-point valued.
      static 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 class  TSP.Integer
      Cost function for the Traveling Salesperson Problem (TSP), where edge costs are integer valued.
      static 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 Detail

      • length

        public final int length()
        Gets the number of cities in the TSP instance.
        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:
        NullPointerException - 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:
        NullPointerException - if i < 0 or i ≥ length().