The Traveling Salesman Problem (TSP) is a classic optimization problem that seeks to find the shortest possible route for a salesman to visit each city once and return to the origin city. This example implements a brute-force approach to solve TSP.

Program Structure

The program consists of three main components:

1. Distance Matrix: A 2D array representing the distances between each pair of cities.
2. Permutation Function: A recursive method that generates all possible routes.
3. Main Method: Initializes the distance matrix and calls the permutation function to calculate the shortest route.

Java Code

import java.util.Arrays;

public class TravelingSalesman {
    
    // Distance matrix representing the distances between cities
    private static final int[][] DISTANCE_MATRIX = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    
    private static int numCities = DISTANCE_MATRIX.length;
    private static boolean[] visited;
    private static int minPathCost = Integer.MAX_VALUE;
    private static int[] bestPath;

    public static void main(String[] args) {
        visited = new boolean[numCities];
        bestPath = new int[numCities + 1]; // To store the best path
        visited[0] = true; // Start from the first city
        findShortestPath(0, 0, 1, new int[numCities + 1]);
        System.out.println("Minimum cost: " + minPathCost);
        System.out.print("Best path: ");
        for (int city : bestPath) {
            System.out.print(city + " ");
        }
    }

    /**
     * Recursively finds the shortest path using backtracking.
     *
     * @param currentCity the current city index
     * @param currentCost the current cost of the path
     * @param level the current level of recursion (number of cities visited)
     * @param path the current path taken
     */
    private static void findShortestPath(int currentCity, int currentCost, int level, int[] path) {
        path[level - 1] = currentCity; // Store the current city in the path

        // If all cities are visited, return to the starting city
        if (level == numCities) {
            currentCost += DISTANCE_MATRIX[currentCity][0]; // Add cost to return to starting city
            if (currentCost < minPathCost) {
                minPathCost = currentCost; // Update minimum cost
                System.arraycopy(path, 0, bestPath, 0, path.length); // Update best path
            }
            return;
        }

        // Explore all other cities
        for (int nextCity = 0; nextCity < numCities; nextCity++) {
            if (!visited[nextCity]) {
                visited[nextCity] = true; // Mark city as visited
                findShortestPath(nextCity, currentCost + DISTANCE_MATRIX[currentCity][nextCity], level + 1, path);
                visited[nextCity] = false; // Backtrack
            }
        }
    }
}

Explanation of the Code

• Distance Matrix: The matrix defines the distances between four cities. In this example, the cities are represented by indices.
• Visited Array: This boolean array keeps track of which cities have been visited during the path exploration.
• findShortestPath Method: This method uses recursion to explore all possible paths. It adds the current city to the path and checks if all cities have been visited. If so, it calculates the total cost and updates the minimum cost and best path if necessary.
• Main Method: Initializes variables, starts the recursive function, and prints the results.

Explanation of the Program Structure

• Distance Matrix: This 2D array defines the distances between each pair of cities. The diagonal (from a city to itself) is zero since there is no distance.
• Visited Array: A boolean array that tracks whether a city has been visited during the current route exploration.
• minPathCost: A variable that stores the minimum path cost found during the exploration.
• bestPath: An array to store the sequence of cities for the optimal path.
• findShortestPath Method: This recursive method generates all possible paths by exploring each city. It keeps track of the current city, cost incurred, and level of recursion (number of cities visited). If all cities have been visited, it checks if the current cost is less than the previously recorded minimum cost.
• Main Method: Initializes the distance matrix and calls the recursive function to start the path exploration. Finally, it prints the minimum cost and the best path found.

Complexity and Limitations

The brute-force approach has a time complexity of O(n!), making it impractical for large numbers of cities. For larger instances of TSP, heuristic or approximation algorithms are recommended.

Conclusion

This Java implementation of the Traveling Salesman Problem provides a straightforward example of using recursion and backtracking to find the optimal route. Although it is limited in scalability, it effectively demonstrates the problem-solving approach.