Java Coding Test Course, Solving the Traveling Salesman Problem

Hello, in this blog post, we will delve deeply into one of the frequently encountered problems in Java coding tests: the “Traveling Salesman Problem.” This problem is very useful for laying the foundations of graph theory and combinatorics, and it serves as a good example to apply various algorithmic techniques.

Problem Description

The Traveling Salesman Problem can be described as follows. The salesman is tasked with finding the shortest path that visits all the given cities and returns to the starting city. All cities are connected, and the distance between any two cities is provided. The goal is to complete the tour of the visited cities with the minimum cost.

Input

  • Number of cities N (2 ≤ N ≤ 10)
  • A cost matrix C of size N x N is provided. C[i][j] represents the cost of traveling from city i to city j. If it is not possible to travel from city i to j, C[i][j] is infinite.

Output

Output the minimum cost to visit all cities once and return to the starting city.

Problem Analysis

This problem is classified as an NP-hard problem, generally solvable with a complete search method. However, since N is limited to a maximum of 10, it can be solved efficiently using a bitmask technique with dynamic programming (DP). By using a bitmask, we can represent the visit status of each city as bits, allowing us to calculate the minimum cost for all possible paths.

Algorithm Design

The basic idea for solving the problem is as follows:

  1. Use a bitmask to indicate the visit state of each city.
  2. Recursively explore all possible paths while calculating the minimum path.
  3. Use memoization to store already calculated minimum costs to avoid redundant calculations.

Key Variables

  • N: Number of cities
  • C[][]: Cost matrix
  • cache: Array for memoization
  • allVisited: Bitmask to check if all cities have been visited
  • start: Starting city

Java Code Implementation

The code below implements the Traveling Salesman Problem according to the given algorithm. Check how each step progresses through the code.


import java.util.Arrays;

public class TravelingSalesman {
    
    static int N; // Number of cities
    static int[][] C; // Cost matrix
    static int[][] cache; // Array for memoization
    static final int INF = Integer.MAX_VALUE; // Infinite value

    public static void main(String[] args) {
        // Example: Number of cities N = 4
        N = 4; 
        C = new int[][]{
            {0, 10, 15, 20},
            {5, 0, 9, 10},
            {6, 13, 0, 12},
            {8, 8, 9, 0}
        };

        // Initialize the memoization array
        cache = new int[1 << N][N];
        for (int i = 0; i < (1 << N); i++) {
            Arrays.fill(cache[i], -1);
        }

        int result = tsp(1, 0); // Start from the initial city 0 having visited all cities
        System.out.println("Minimum cost: " + result);
    }

    static int tsp(int visited, int pos) {
        // Base case: when all cities have been visited
        if (visited == (1 << N) - 1) {
            return C[pos][0] == 0 ? INF : C[pos][0]; // Cost to return to the starting city
        }

        // If already computed
        if (cache[visited][pos] != -1) {
            return cache[visited][pos];
        }

        int answer = INF;

        // Check all cities
        for (int city = 0; city < N; city++) {
            // If the city hasn't been visited yet
            if ((visited & (1 << city)) == 0 && C[pos][city] != 0) {
                int newVisited = visited | (1 << city);
                int newCost = C[pos][city] + tsp(newVisited, city);
                answer = Math.min(answer, newCost);
            }
        }

        return cache[visited][pos] = answer; // Store the minimum cost
    }
}

Code Explanation

  1. Main Method: Initializes the number of cities and the cost matrix with the example, calls the TSP function, and outputs the result.
  2. tsp Method: Recursively calculates the minimum cost based on the bitmask and current city information.
  3. Base Case: When all cities have been visited, returns the cost to return to the starting city.
  4. Memoization: Already computed states are stored in the cache array and reused as needed to enhance efficiency.

Results

The above code calculates the minimum cost for the provided cities and cost matrix. The output is the minimum cost to visit all cities and return to the starting city. You can input your own cost matrix using this code and check the results, which will help you understand the flow of the algorithm.

Conclusion

Through this tutorial, we learned how to solve the Traveling Salesman Problem using dynamic programming and bitmasks. This problem frequently appears in coding tests and will significantly aid in learning fundamental algorithmic techniques to tackle such challenges. Like other algorithm problems, there are multiple ways to approach the problem. Try various solutions to enhance your algorithm skills.

Stay tuned for our next post, where we will cover another problem. If you have any questions or comments, please leave them below. Thank you!