Package io.openml.gearbox

Class TravelingSalesman

java.lang.Object

io.openml.gearbox.TravelingSalesman

public final class TravelingSalesman
extends Object

Solves the Traveling Salesman Problem (TSP) using the Held-Karp algorithm, which employs dynamic programming with bitmasking.

At its heart, the Traveling Salesman Problem asks a simple question: "Given a list of cities and the distances between each pair, what is the shortest possible route that visits each city exactly once and returns to the origin city?"

This implementation finds the exact optimal solution and is suitable for a small number of cities (e.g., up to ~22) due to its O(n^2 * 2^n) time complexity.

The class is marked as `final` to signify that its algorithmic implementation is complete and not designed for extension, ensuring its logical integrity.

Other references on traveling salesman problem include:

• Introduction to Algorithms by CLRS (Cormen, Leiserson, Rivest, and Stein), 3rd ed, sections 34.5.4 & 35.2
• The Algorithm Design Manual * by Steven S. Skiena, 3rd ed, section 19.4

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static final record	TravelingSalesman.Tour	A record to immutably hold the result of the TSP calculation.

Constructor Summary

Constructors

Constructor	Description
TravelingSalesman(double[][] distanceMatrix)	Constructor.

Method Summary

Modifier and Type	Method	Description
TravelingSalesman.Tour	solve()	Executes the dynamic programming algorithm to find the optimal tour.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

TravelingSalesman

public TravelingSalesman(double[][] distanceMatrix)

Constructor.

Prepares the solver for a given set of cities and their distances.

Parameters:

distanceMatrix - A square matrix where matrix[i][j] represents the distance from city i to city j.

Throws:

IllegalArgumentException - if distanceMatrix is null, or empty, or non-squarely shaped

Method Details

solve

public TravelingSalesman.Tour solve()

Executes the dynamic programming algorithm to find the optimal tour.

Returns:

A Tour record containing the minimum cost and the sequence of cities in the optimal path.