Scribd
Upload
78 views3 pages

Assignment 13 TSP

The document presents an assignment to implement and solve the Traveling Salesman Problem (TSP) using both dynamic programming (exact) and greedy (approximation) algorithms. The dynamic programming solution calculates a minimum distance of 122, while the greedy algorithm outputs a shortest path of 1 4 5 2 3 1 with a minimum cost of 55. Both implementations are provided in C code format.

Uploaded by

roysayanccp05
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
78 views3 pages

Assignment 13 TSP

The document presents an assignment to implement and solve the Traveling Salesman Problem (TSP) using both dynamic programming (exact) and greedy (approximation) algorithms. The dynamic programming solution calculates a minimum distance of 122, while the greedy algorithm outputs a shortest path of 1 4 5 2 3 1 with a minimum cost of 55. Both implementations are provided in C code format.

Uploaded by

roysayanccp05
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Assignment – 13

To implement and solve the Traveling Salesman Problem (TSP) using both (a) exact (dynamic
programming) and (b) approximation (greedy) algorithms.

Code:

(a) Using Dynamic Programming Algorithm

#include <stdio.h>
#include <limits.h>
#define MAX 9999
int n = 4;
int distan[20][20] = {
{0, 22, 26, 30},
{30, 0, 45, 35},
{25, 45, 0, 60},
{30, 35, 40, 0}};
int DP[32][8];
int TSP(int mark, int position) {
int completed_visit = (1 << n) - 1;
if (mark == completed_visit) {
return distan[position][0];
}
if (DP[mark][position] != -1) {
return DP[mark][position];
}
int answer = MAX;
for (int city = 0; city < n; city++) {
if ((mark & (1 << city)) == 0) {
int newAnswer = distan[position][city] + TSP(mark | (1 << city), city);
answer = (answer < newAnswer) ? answer : newAnswer;
}
}
return DP[mark][position] = answer;
}
int main() {
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
DP[i][j] = -1;
}
}
printf("Minimum Distance Travelled -> %d\n", TSP(1, 0));
return 0;
}

Output:

Minimum Distance Travelled -> 122


(b) Using Greedy Algorithm

#include <stdio.h>
int tsp_g[10][10] = {
{12, 30, 33, 10, 45},
{56, 22, 9, 15, 18},
{29, 13, 8, 5, 12},
{33, 28, 16, 10, 3},
{1, 4, 30, 24, 20}
};
int visited[10], n, cost = 0;

/* creating a function to generate the shortest path */


void travellingsalesman(int c){
int k, adj_vertex = 999;
int min = 999;

/* marking the vertices visited in an assigned array */


visited[c] = 1;

/* displaying the shortest path */


printf("%d ", c + 1);

/* checking the minimum cost edge in the graph */


for(k = 0; k < n; k++) {
if((tsp_g[c][k] != 0) && (visited[k] == 0)) {
if(tsp_g[c][k] < min) {
min = tsp_g[c][k];
adj_vertex = k;
}
}
}
if(min != 999) {
cost = cost + min;
}
if(adj_vertex == 999) {
adj_vertex = 0;
printf("%d", adj_vertex + 1);
cost = cost + tsp_g[c][adj_vertex];
return;
}
travellingsalesman(adj_vertex);
}

/* main function */
int main(){
int i, j;
n = 5;
for(i = 0; i < n; i++) {
visited[i] = 0;
}
printf("Shortest Path: ");
travellingsalesman(0);
printf("\nMinimum Cost: ");
printf("%d\n", cost);
return 0;
}

Output:

Shortest Path: 1 4 5 2 3 1
Minimum Cost: 55

You might also like