C++ Coding Test Course, The Salesman’s Dilemma

The Traveling Salesman Problem (TSP) is one of the classic algorithm problems, also known as the “Salesman’s Dilemma”.
The problem involves finding the shortest possible route that visits a set of cities and returns to the origin city.
It falls under the category of combinatorial optimization problems and is classified as NP-hard.
Therefore, while small datasets can be solved using brute force algorithms, larger datasets require more efficient approaches.

Problem Description

Given N cities and a distance matrix between each pair of cities, the goal is to calculate the sum of the distances of the shortest route that visits each city exactly once before returning to the starting point.
Below is the format of the problem.

        
        Input:
        N (number of cities)
        Distance matrix (nxn matrix)
        
        Output:
        Length of the shortest route
        
    

Example

Input Example:

        4
        0 10 15 20
        10 0 35 25
        15 35 0 30
        20 25 30 0
    

Output Example:
80

Problem Solving Process

There are several approaches to solving this problem, and here we will use two methods: brute force and dynamic programming (DP) to solve the problem.

1. Brute Force Method

The brute force method searches through all possible paths to find the shortest route.
It generates all permutations of cities and calculates the total distance for each path, then finds the minimum distance among them.

Algorithm Description

1. Generate all permutations of the cities.
2. Calculate the total distance for each permutation.
3. Find the minimum distance among the calculated distances.

C++ Code Example

        
        #include 
        #include 
        #include 
        #include 

        using namespace std;

        int calculateDistance(const vector>& dist, const vector& path) {
            int totalDistance = 0;
            for (int i = 0; i < path.size() - 1; i++) {
                totalDistance += dist[path[i]][path[i + 1]];
            }
            totalDistance += dist[path.back()][path[0]]; // Return to start
            return totalDistance;
        }

        int main() {
            int N;
            cin >> N;
            vector> dist(N, vector(N, 0));

            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    cin >> dist[i][j];

            vector cities(N);
            for (int i = 0; i < N; i++) cities[i] = i;

            int minDistance = INT_MAX;

            do {
                int currentDistance = calculateDistance(dist, cities);
                minDistance = min(minDistance, currentDistance);
            } while (next_permutation(cities.begin() + 1, cities.end())); // Fix first city

            cout << minDistance << endl;

            return 0;
        }
        
    

2. Dynamic Programming (DP) Method

The dynamic programming method efficiently uses memory.
It represents cities using a bitmask to indicate whether each city has been visited, and utilizes recursion and memoization to compute the shortest route.
In this case, the complexity is reduced to O(n^2 * 2^n). Below is an explanation of the dynamic programming solution.

Algorithm Description

1. Use a bitmask to represent whether each city has been visited.
2. Initialize a minimum cost table and set it to 0.
3. Explore possible paths through a recursive function, updating the minimum distance value.

C++ Code Example

        
        #include 
        #include 
        #include 

        using namespace std;

        int tsp(int pos, int visited, const vector>& dist, vector>& memo) {
            if (visited == ((1 << dist.size()) - 1)) {
                return dist[pos][0]; // Return to the start city
            }

            if (memo[pos][visited] != -1) {
                return memo[pos][visited];
            }

            int minCost = INT_MAX;

            for (int city = 0; city < dist.size(); city++) {
                if ((visited & (1 << city)) == 0) {
                    int newCost = dist[pos][city] + tsp(city, visited | (1 << city), dist, memo);
                    minCost = min(minCost, newCost);
                }
            }

            return memo[pos][visited] = minCost;
        }

        int main() {
            int N;
            cin >> N;
            vector> dist(N, vector(N, 0));

            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    cin >> dist[i][j];

            vector> memo(N, vector((1 << N), -1));

            cout << tsp(0, 1, dist, memo) << endl;

            return 0;
        }
        
    

Conclusion

In this tutorial, we explored the Traveling Salesman Problem implemented in C++, covering the problem definition, examples,
and detailed approaches using brute force and dynamic programming methods.
It is important to note that the brute force method should only be used when the number of cities is small, as it becomes less efficient with increasing numbers of cities.
Such algorithmic problems frequently appear in coding tests and interviews, so sufficient practice is required.