Implement any scheme to find the optimal solution for the travelling salesman problem

Travelling Salesman Problem Using Nearest Neighbour Algorithm in C

The Nearest Neighbour (NN) algorithm is a greedy heuristic method for solving the Travelling Salesman Problem (TSP). Though it doesn’t guarantee the optimal solution, it provides a quick and fairly efficient approximation, especially useful for large datasets where brute-force or dynamic programming becomes infeasible.

/* Nearest neighbour algorithm for travelling sales person*/
#include<stdio.h>
#include<conio.h>

#define MAX 100
#define INFINTIY 999

int n, a[MAX][MAX];
int visited[MAX], nn_cost=0;
void get_distance()
{
int i,j;
//for dynamic data
/* 
printf("Enter no. of cities:\n");
scanf("%d", &n);
printf("\n Enter cost Matrix: \n");
for(i=0;i<n;i++)
{
printf("\n Enter Elements of Row #: %d (999 for no connectivity)\n", i+1);
for(j=0;j<n;j++)
scanf("%d, &a[i][j]);
visited[i] = 0;//for nn method
}
*/
n = 4;
a[0][0] = INFINITY;
a[0][1] = 1;
a[0][2] = 3;
a[0][3] = 6;

a[1][0] = 1;
a[1][1] = INFINITY;
a[1][2] = 2;
a[1][3] = 3;

a[2][0] = 3;
a[2][1] = 2;
a[2][2] = INFINITY;
a[2][3] = 1;

a[3][0] = 6;
a[3][1] = 3;
a[3][2] = 1;
a[3][3] = INFINITY;

Visited[0] = 0;
Visited[1] = 0;
Visited[2] = 0;
Visited[3] = 0;

printf("\n\n The cost list is:\n\n");
for(i=0;i<n;i++)
{
printf("\n\n");
for(j=0;j<n;j++)
printf("\t%d",a[i][j]);
}
}
int least(int c)
{
int i, nc=INFINITY;
int min=INFINITY;

for(i=0;i<n;i++)
{
if((a[c][i] !=0) && (visited[i] == 0))
if(a[c][i]<min)
{
//min = a[i][0]+a[c][i];
min = a[c][i];
nc = i;
}
}
if(min != INFINITY)
nn_cost += min;
return nc;
}
void nn_mincost(int city)
{
int ncity;
visited[city] = 1;
printf("%d > ",city);
ncity = least(city);
if(ncity == INFINITY)
{
ncity = 0;
printf("%d",ncity);
nn_cost += a[city][ncity];
return;
}
nn_mincost(ncity);
return;
}

int tsp_nn()
{
printf("\n\n The Traversal path using approximation:\n\n");
//min=mincost(0);
nn_mincost(0);

printf("\n\n Minimum cost is: ");
printf("%d", nn_cost);
return nn_cost;
}

int tsp_dp(int c[][MAX], int tour[], int start, int n)
{
int i,j,k;//loop counters
int temp[MAX];/* Temporary during calculations*/
int mintour[MAX]; /* Minimal tour array*/
int mincost; /*Minimal cost*/
int ccost;/*Current cost*/

/*End of recurssion condition.*/
if(start == n-2)
return c[tour[n-2]][tour[n-1]] + c[tour[n-1][0]];

/* Compute the tour starting from the current city.*/
mincost = INFINITY;
for(i = start+1; i<n; i++)
{
for(j=0; j<n; j++)
temp[j] = tour[j];

/* Adjust positions*/
temp[start+1] = tour[i];
temp[i] = tour[start+1];

/* Found a better cycle?? (recurrrence derivable)*/
if(c[tour[start]][tour[i]] + (ccost = tsp_dp(c,temp,start+1, n)) < mincost)
{
mincost = c[tour[start]][tour[i]] + ccost;
for(k=0; k<n; k++)
mintour[k] = temp[k];
}
}
/* Set the minimum tour array*/
for(i=0; i<n; i++)
tour[i] = mintour[i];
return mincost;
}

int tsp_dyn()
{
int i; /*Loop counters*/
int tour[MAX];/* Tour Matrix*/
int dyn_min_cost; /*Least Cost*/

for(i=0;i<n;i++)
tour[i] = i;
dyn_min_cost = tsp_dp(a, tour, 0,n);
printf("\n\n\n Traversal Path using Dynamic Programming: \n\n");
for(i=0;i<n;i++)
printf("%d > ", tour[i]);
printf("0\n");
printf("\n Minimum cost: %d", dyn_min_cost);
return dyn_min_cost;
}

int main()
{
int nn_cost,dyn_cost;
double err;
clrscr();
get_distance();
nn_cost = tsp_nn();
dyn_cost = tsp_dyn();
err = (double)nn_cost/(double)dyn_cost;
printf("\n\n\n Error Ratio: %f", err);
getch();
return 0;
}

OUTPUT
The cost matrix list is:
999	1	3	6
1	999	2	3
3	2	999	1
6 	3 	1 	999

The traversal path using approximation:
0>1>2>3>0
Minimum cost is:10

The traversal path using dynamic programming:
0>1>3>2>0
Minimum cost: 8

Error ration: 1.250000