Travelling Salesman Problem In C

Dynamic programming is a powerful technique for addressing optimization challenges by breaking them down into smaller subproblems and saving the solutions to avoid redundant computations. The following steps can also be applied to tackle the Traveling Salesman Problem (TSP) using dynamic programming:

Definition of a subproblem:

Now, we will specify our subtasks as follows: dpmask, where 'mask' represents a binary numeral indicating the set of cities visited, and 'i' signifies the present city. The variable dpmask will hold the minimum cost required to visit all cities in the "mask" and conclude the journey at city "i".

Primary Case:

When 'mask' contains only a single city (i.e., when there is only one bit set in the binary representation of 'mask'), set dpmask to a large number to represent infinity.

Relation of Recurrence:

Iterate over all cities 'j' that are not part of the 'mask' for each specific issue dpmask, and calculate the expense of traveling to city 'j' from any city 'k' within the 'mask' that has been visited. Incorporate the minimum cost into dpmask | (1 j).

Final Response:

The minimum value of dp[(1 n) - 1)]'s final result will be determined. Here, '[i]' represents the individual city index, with 'n' indicating the total count of cities.

Recursive Equation

The recursive formula for solving the Traveling Salesman Problem using dynamic programming is as outlined below:

Calculate the minimum value for dpmask by finding the smallest sum of dpmask ^ (1 << j) + costi among all j not present in the mask.

In this scenario, the costi represents the distance between the cities 'i' and 'j'.

dpmask: This represents the minimum expense incurred for visiting all cities specified in the binary mask "mask", beginning from city "i". The binary "mask" is a numerical representation where the jth bit is enabled (set to 1) if city j is included in the travel itinerary, and disabled (set to 0) if the city has not been visited yet.

By toggling the jth bit in the "mask" using the expression mask ^ (1 << j), a fresh mask is generated, indicating the visitation of city "j". This process involves a bitwise XOR operation with the result of a left shift.

The cost of traveling from city 'i' to city 'j' is determined by the value stored in costi within the cost matrix containing travel durations between all city pairs.

Time Complexity

The dynamic programming method, with 'n' representing the city count, requires O(n2 * 2n) time complexity to address the Traveling Salesman Problem (TSP). This is due to the existence of 2n possible city subsets, necessitating iteration over 'n' cities for every subset to identify the least costly route.

Example:

Let's consider a program for the Travelling Salesman Problem implemented in the C programming language:

#include <stdio.h>
#include <limits.h>

#define MAX_N 15 // Maximum number of cities

int n; // Number of cities
int cost[MAX_N][MAX_N]; // Cost matrix
int dp[1 << MAX_N][MAX_N]; // Dynamic programming table

int tsp(int mask, int pos) {
    if (mask == (1 << n) - 1) {
        return cost[pos][0]; // Return to the starting city
    }

    if (dp[mask][pos] != -1) {
        return dp[mask][pos];
    }

    int ans = INT_MAX;
    for (int next = 0; next < n; next++) {
        if ((mask & (1 << next)) == 0) { // If city 'next' is not visited
            int newCost = cost[pos][next] + tsp(mask | (1 << next), next);
            ans = min(ans, newCost);
        }
    }

    return dp[mask][pos] = ans;
}

int main() {
    printf("Enter the number of cities: ");
    scanf("%d", &n);

    printf("Enter the cost matrix:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &cost[i][j]);
        }
    }

    memset(dp, -1, sizeof(dp));

    int minCost = tsp(1, 0); // Start from city 0

    printf("Minimum cost of the TSP: %d\n", minCost);

    return 0;
}

Output:

Enter the number of cities: 4
Enter the cost matrix:
0 10 15 20