 java.lang.Object

 org.cicirello.search.problems.tsp.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 floatingpoint valued (class
TSP.Double
), and one for integer cost edges (classTSP.Integer
). And it also provides two inner classes where the edge weights are precomputed, one for edge costs that are floatingpoint valued (classTSP.DoubleMatrix
), and one for integer cost edges (classTSP.IntegerMatrix
). The nested classes with precomputed edge weights (TSP.DoubleMatrix
andTSP.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
andTSP.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 floatingpoint valued.static class
TSP.DoubleMatrix
Cost function for the Traveling Salesperson Problem (TSP), where edge costs are floatingpoint 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 Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description double
getX(int i)
Gets the x coordinate of a city.double
getY(int i)
Gets the y coordinate of a city.int
length()
Gets the number of cities in the TSP instance.



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().

