TravelingSalesman.java

packagecom.thealgorithms.graph;

importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.Collections;
importjava.util.List;

/**
 * This class provides solutions to the Traveling Salesman Problem (TSP) using both brute-force and dynamic programming approaches.
 * For more information, see <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem">Wikipedia</a>.
 * @author <a href="https://github.com/DenizAltunkapan">Deniz Altunkapan</a>
 */

publicfinalclassTravelingSalesman {

// Private constructor to prevent instantiation
privateTravelingSalesman() {
 }

/**
 * Solves the Traveling Salesman Problem (TSP) using brute-force approach.
 * This method generates all possible permutations of cities, calculates the total distance for each route, and returns the shortest distance found.
 *
 * @param distanceMatrix A square matrix where element [i][j] represents the distance from city i to city j.
 * @return The shortest possible route distance visiting all cities exactly once and returning to the starting city.
 */
publicstaticintbruteForce(int[][] distanceMatrix) {
if (distanceMatrix.length <= 1) {
return0;
 }

List<Integer> cities = newArrayList<>();
for (inti = 1; i < distanceMatrix.length; i++) {
cities.add(i);
 }

List<List<Integer>> permutations = generatePermutations(cities);
intminDistance = Integer.MAX_VALUE;

for (List<Integer> permutation : permutations) {
List<Integer> route = newArrayList<>();
route.add(0);
route.addAll(permutation);
intcurrentDistance = calculateDistance(distanceMatrix, route);
if (currentDistance < minDistance) {
minDistance = currentDistance;
 }
 }

returnminDistance;
 }

/**
 * Computes the total distance of a given route.
 *
 * @param distanceMatrix A square matrix where element [i][j] represents the
 * distance from city i to city j.
 * @param route A list representing the order in which the cities are visited.
 * @return The total distance of the route, or Integer.MAX_VALUE if the route is invalid.
 */
publicstaticintcalculateDistance(int[][] distanceMatrix, List<Integer> route) {
intdistance = 0;
for (inti = 0; i < route.size() - 1; i++) {
intd = distanceMatrix[route.get(i)][route.get(i + 1)];
if (d == Integer.MAX_VALUE) {
returnInteger.MAX_VALUE;
 }
distance += d;
 }
intreturnDist = distanceMatrix[route.get(route.size() - 1)][route.get(0)];
return (returnDist == Integer.MAX_VALUE) ? Integer.MAX_VALUE : distance + returnDist;
 }

/**
 * Generates all permutations of a given list of cities.
 *
 * @param cities A list of cities to permute.
 * @return A list of all possible permutations.
 */
privatestaticList<List<Integer>> generatePermutations(List<Integer> cities) {
List<List<Integer>> permutations = newArrayList<>();
permute(cities, 0, permutations);
returnpermutations;
 }

/**
 * Recursively generates permutations using backtracking.
 *
 * @param arr The list of cities.
 * @param k The current index in the permutation process.
 * @param output The list to store generated permutations.
 */
privatestaticvoidpermute(List<Integer> arr, intk, List<List<Integer>> output) {
if (k == arr.size()) {
output.add(newArrayList<>(arr));
return;
 }
for (inti = k; i < arr.size(); i++) {
Collections.swap(arr, i, k);
permute(arr, k + 1, output);
Collections.swap(arr, i, k);
 }
 }

/**
 * Solves the Traveling Salesman Problem (TSP) using dynamic programming with the Held-Karp algorithm.
 *
 * @param distanceMatrix A square matrix where element [i][j] represents the distance from city i to city j.
 * @return The shortest possible route distance visiting all cities exactly once and returning to the starting city.
 * @throws IllegalArgumentException if the input matrix is not square.
 */
publicstaticintdynamicProgramming(int[][] distanceMatrix) {
if (distanceMatrix.length == 0) {
return0;
 }
intn = distanceMatrix.length;

for (int[] row : distanceMatrix) {
if (row.length != n) {
thrownewIllegalArgumentException("Matrix must be square");
 }
 }

int[][] dp = newint[n][1 << n];
for (int[] row : dp) {
Arrays.fill(row, Integer.MAX_VALUE);
 }
dp[0][1] = 0;

for (intmask = 1; mask < (1 << n); mask++) {
for (intu = 0; u < n; u++) {
if ((mask & (1 << u)) == 0 || dp[u][mask] == Integer.MAX_VALUE) {
continue;
 }
for (intv = 0; v < n; v++) {
if ((mask & (1 << v)) != 0 || distanceMatrix[u][v] == Integer.MAX_VALUE) {
continue;
 }
intnewMask = mask | (1 << v);
dp[v][newMask] = Math.min(dp[v][newMask], dp[u][mask] + distanceMatrix[u][v]);
 }
 }
 }

intminDistance = Integer.MAX_VALUE;
intfullMask = (1 << n) - 1;
for (inti = 1; i < n; i++) {
if (dp[i][fullMask] != Integer.MAX_VALUE && distanceMatrix[i][0] != Integer.MAX_VALUE) {
minDistance = Math.min(minDistance, dp[i][fullMask] + distanceMatrix[i][0]);
 }
 }

returnminDistance == Integer.MAX_VALUE ? 0 : minDistance;
 }
}