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
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 floatingpoint 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 floatingpoint 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
Modifier and TypeClassDescriptionstatic final class
Cost function for the Traveling Salesperson Problem (TSP), where edge costs are floatingpoint valued.static final class
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 final class
Cost function for the Traveling Salesperson Problem (TSP), where edge costs are integer valued.static final class
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
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. 
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().
