Traveling Salesman Problem (TSP)

Traveling Salesman Problem (TSP)

GitHub Repository

Explanation of the code.

This code implements a brute-force solution to the Traveling Salesman Problem (TSP) for five cities.

The goal is to find the shortest round-trip route that visits each city exactly once and returns to the starting point.

Key Parts of the Code :

1. Distance Matrix (distMatrix):

A vector(vector(int)) matrix represents distances between each pair of cities. For example, distMatrix[0][1] is the distance from city A to city B.

INT_MAX is used to represent an unreachable path between two cities, making the route invalid if it includes that segment.

// INT_MAX = unreachable paths
    const vector<vector<int>> dist_matrix =
        {
        {0, 2, 2, INT_MAX, INT_MAX}, // A
        {2, 0, 3, 3, 1},            // B
        {2, 3, 0, 1, 3},           // C
        {INT_MAX, 3, 1, 0, 3},    // D
        {INT_MAX, 1, 3, 3, 0}    // E
        };

2. Route Representation:

Cities are indexed (e.g., 0 for A, 1 for B, etc.), and the route is stored as a vector(int).

The cityNames vector maps city indices to names for more readable output when printing the final route.

3. calculateDistance Function:

This function calculates the total distance of a route, ensuring that every leg of the route is reachable.

int calculateDistance(const vector<vector<int>>& dist_matrix, const vector<int>& route)
{
    int totalDistance = 0;
    for (int i = 0; i < (int)route.size() - 1; i++)
    {
        if (dist_matrix[route[i]][route[i + 1]] == INT_MAX) // Check for unreachable path
        {
            return INT_MAX; // Unreachable (stupidly high num)
        }
        totalDistance += dist_matrix[route[i]][route[i + 1]];
    }
    // Check return path
    if (dist_matrix[route[route.size() - 1]][route[0]] == INT_MAX) 
    {
        return INT_MAX;
    }
    totalDistance += dist_matrix[route[route.size() - 1]][route[0]];
    return totalDistance;
}

Inputs:

distMatrix: The distance matrix for city pairs.

route: The tested route, represented as a sequence of city indices.

How It Works:

Loop through the Route:

The distance between each pair of consecutive cities in the route is added to the total distance.

Unreachable Path Check:

If any distance is INT_MAX, the function immediately returns INT_MAX, marking the route as unreachable.

Return to Start Check:

After looping through all pairs in the route, the distance from the last city back to the starting city is added. If this distance is INT_MAX, the route is unreachable.

// Try every possible route by generating permutations
    do
    {
        const int current_distance = calculateDistance(dist_matrix, cities);
        if (current_distance < minDistance)
        {
            minDistance = current_distance;
            bestRoute = cities;
        }
    }
    while (next_permutation(cities.begin() + 1, cities.end())); // Fix the first city to reduce duplicate routes

Output:

The function returns the total distance for the route if it is valid, or INT_MAX if any segment is unreachable.

// Output the results
    cout << "Minimum distance : " << minDistance << '\n';
    cout << "Best route : ";
    for (const int city : bestRoute)
    {
        cout << cityNames[city] << " ";
    }
    cout << cityNames[bestRoute[0]] << '\n'; // Return to starting city

    return 0;

4. Main Algorithm (Main Function):

Initialization:

distMatrix defines distances between cities.

cities holds indices representing each city.

cityNames is used to translate city indices to names for output.

minDistance is initialized to INT_MAX to track the minimum distance found.

bestRoute stores the optimal route.

Generating Permutations:

The program generates all possible routes by permutating cities (except the first city, which is fixed for optimization).

Route Evaluation:

For each permutation of cities, calculateDistance() computes the route's total distance.

If the distance is smaller than minDistance, the route and its distance become the new bestRoute and minDistance.

Output:

After evaluating all permutations, the program prints the minimum distance and the optimal route (in terms of city names).

5. Additional Notes

next_permutation:

This function generates the next lexicographical permutation of the cities vector, enabling a brute-force approach to try all possible city sequences.

Fixing the first city (using cities.begin() + 1) avoids duplicate routes that differ only in starting points.

Efficiency:

This brute-force approach has factorial time complexity (O(n! * n)), so it only works efficiently with a small number of cities.

For more than 5-10 cities, more advanced algorithms like Dynamic Programming (Held-Karp algorithm) or Heuristic Methods (e.g., Nearest Neighbor, Simulated Annealing) are needed to solve the problem in a reasonable time frame.

bye, bye.