NUHMAN.com

The Traveling Salesman Problem (TSP) is a famous optimization challenge. The goal? To find the shortest possible route that visits every city exactly once and returns to the starting point.

It’s a classic example of NP-Hard problems — easy to describe but computationally expensive to solve for large inputs. Here’s a clean Java implementation using a brute-force approach.

🧩 Problem Setup

Given a distance matrix between cities, calculate the minimum route cost that visits all cities and loops back to the origin.

💻 Java Code – Brute Force TSP

java

import java.util.Arrays;

public class TravelingSalesmanProblem {

    private static final int N = 4; // Number of cities

    // Distance matrix (symmetric)
    private static final int[][] DISTANCE_MATRIX = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };

    // Calculate total cost of a tour
    private static int calculateTourCost(int[] tour) {
        int totalCost = 0;
        for (int i = 0; i < N - 1; i++) {
            totalCost += DISTANCE_MATRIX[tour[i]][tour[i + 1]];
        }
        totalCost += DISTANCE_MATRIX[tour[N - 1]][tour[0]]; // Return to start
        return totalCost;
    }

    // Recursive function to explore all permutations (tours)
    private static void findShortestTour(int[] tour, boolean[] visited, int currentIndex, int[] minTour, int[] minCost) {
        if (currentIndex == N) {
            int currentCost = calculateTourCost(tour);
            if (currentCost < minCost[0]) {
                minCost[0] = currentCost;
                System.arraycopy(tour, 0, minTour, 0, N); // Save best tour
            }
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                tour[currentIndex] = i;
                findShortestTour(tour, visited, currentIndex + 1, minTour, minCost);
                visited[i] = false; // Backtrack
            }
        }
    }

    public static void main(String[] args) {
        int[] tour = new int[N];              // Current tour
        boolean[] visited = new boolean[N];   // Visited cities
        int[] minTour = new int[N];           // Shortest tour found
        int[] minCost = {Integer.MAX_VALUE};  // Min cost found

        findShortestTour(tour, visited, 0, minTour, minCost);

        System.out.println("Shortest tour: " + Arrays.toString(minTour));
        System.out.println("Minimum cost: " + minCost[0]);
    }
}

🧠 Key Concepts

📊 Data Structures

• DISTANCE_MATRIX: 2D array holding pairwise distances.
• tour[]: Current path being evaluated.
• visited[]: Keeps track of visited cities.
• minTour[]: Stores the best (shortest) tour found.
• minCost[]: Holds the minimum distance found.

⚙️ How It Works

1. calculateTourCost:
2. Sums distances of a tour and completes the cycle by returning to the starting city.
3. findShortestTour:
4. Uses recursion + backtracking to try all permutations of the cities and tracks the minimum cost tour.
5. main:
6. Initializes everything and kicks off the search. Finally prints the best tour and its cost.

📌 Sample Output

yaml

Shortest tour: [0, 1, 3, 2]
Minimum cost: 80

(The exact tour may vary due to permutation order, but the cost will be minimal.)

⚠️ Limitations

• 🚫 Not suitable for large N due to O(N!) complexity.
• ✅ Great for educational purposes and understanding recursion/backtracking.

🚀 Going Further

For larger inputs, explore:

• Dynamic Programming (Held-Karp)
• Branch and Bound
• Genetic Algorithms
• Ant Colony Optimization

🔚 Summary

• Brute force TSP in Java is a great starting point for learning permutations and recursive backtracking.
• Use this approach for up to 8–10 cities.
• Beyond that? It’s time to bring in optimization and heuristics.