TRAVELING SALESMAN PROBLEM USING DYNAMIC APPROACH

The Traveling Salesman Problem (TSP) is a classic optimization problem in computer science. The problem involves finding the shortest possible route that a salesman must take to visit a set of cities and return to the starting point. The dynamic programming approach to solving the TSP involves breaking the problem down into subproblems and storing the solutions to these subproblems in a table. Here's how you can implement a C program to solve the TSP using dynamic programming.

To solve aTSP using C Programming

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_CITIES 10

int num_cities;
int city_coords[MAX_CITIES][2];
double dist[MAX_CITIES][MAX_CITIES];
double dp[MAX_CITIES][1 << MAX_CITIES];

double tsp(int curr_city, int visited);

int main() {
    int i, j;
    printf("Enter the number of cities: ");
    scanf("%d", &num_cities);
    printf("Enter the coordinates of the cities:\n");
    for (i = 0; i < num_cities; i++) {
        printf("City %d: ", i+1);
        scanf("%d %d", &city_coords[i][0], &city_coords[i][1]);
    }
    printf("\n");

    // Calculate the distances between cities
    for (i = 0; i < num_cities; i++) {
        for (j = 0; j < num_cities; j++) {
            if (i == j) {
                dist[i][j] = 0;
            } else {
                dist[i][j] = sqrt(pow(city_coords[i][0]-city_coords[j][0], 2) + pow(city_coords[i][1]-city_coords[j][1], 2));
            }
        }
    }

    // Solve the TSP using dynamic programming
    double min_dist = tsp(0, 1);
    printf("The minimum distance is: %.2f\n", min_dist);
    return 0;
}

double tsp(int curr_city, int visited) {
    if (visited == (1 << num_cities) - 1) {
        // All cities have been visited, return the distance to the starting city
        return dist[curr_city][0];
    }
    if (dp[curr_city][visited] != 0) {
        // This subproblem has already been solved, return the stored solution
        return dp[curr_city][visited];
    }

    double min_distance = INFINITY;
    int i;
    for (i = 0; i < num_cities; i++) {
        if (!(visited & (1 << i))) {
            // Visit the unvisited city i
            double distance = dist[curr_city][i] + tsp(i, visited | (1 << i));
            if (distance < min_distance) {
                min_distance = distance;
            }
        }
    }

    // Store the solution to this subproblem
    dp[curr_city][visited] = min_distance;
    return min_distance;
}

Programming Explanation:

• First, we define some constants and variables to represent the input data and the dynamic programming table. We assume that the maximum number of cities is 10.
• Next, we ask the user to input the number of cities and their coordinates. We store the coordinates in a 2D array.
• We calculate the distances between all pairs of cities using the distance formula.
• We call the tsp function with the starting city (city 0) and the visited set containing only city 0. The tsp function uses recursion to break down the problem into subproblems and stores the solutions to these subproblems in the dp table. The visited parameter is represented as a bitmask where the i-th bit is set to 1 if city i has been visited, and 0 otherwise.
• In the tsp function, we first check if we have already solved this subproblem by checking if the corresponding entry in the dp table is non-zero.
• If the subproblem has not been solved, we iterate over all unvisited cities and compute the distance to each of them. We then recursively call the tsp function with the new city and the updated visited set, and add the distance to the current city. We keep track of the minimum distance seen so far.
• Finally, we store the minimum distance in the dp table and return it.

The time complexity of this algorithm is O(n^2 * 2^n), where n is the number of cities. The space complexity is also O(n^2 * 2^n). However, in practice, this algorithm can only handle small instances of the TSP due to its high time and space complexity. For larger instances, approximate algorithms such as the nearest neighbor algorithm or the 2-opt algorithm are used.

Output:

The output of the program will be the minimum distance required to travel all the cities and return to the starting city. Here's an example output for a 4-city TSP:

Enter the number of cities: 4
Enter the coordinates of the cities:
City 1: 0 0
City 2: 3 1
City 3: 2 5
City 4: -1 3

The minimum distance is: 12.24

This means that the shortest possible route to travel all four cities and return to the starting city is 12.24 units long. Note that this output may differ depending on the input cities and their coordinates.