In C using recursion: In this program you will take a small Traveling Saleperson
ID: 3817564 • Letter: I
Question
In C using recursion:
In this program you will take a small Traveling Saleperson Problem (TSP) and generate an optimal solution for that input data. When I say a small data set I mean a TSP for 13 or fewer cities. The ONLY way you can guarantee an optimal solution is to generate all possible tours, evaluate the value (sum of all the weights on the edges included in the tour) and remember the smallest such value. I strongly suggest that you use recursion to generate all tours, both because it will help strengthen you recursive program techniques AND because its easier. To make the task easier, each TSP input file will be a complete graph, meaning that is it has 10 cities, each of the 10 will have an edge to each of the other 9 cities.
If you look at the directory you'll find different sized input files and a correct output for each such file. Of course, input10 shows just one set of edge weights for a 10-city problem, and we'll change those edge weights in the examples we use to test your program.
You can use either C or C++ for your program as long as it runs correctly on the CSE machines. You WILL use redirected input to test access data in your program. So, if you have a tsp.cpp file as your program, we'll compile it as
g++ *.cpp
./a.out < input12 (or some other input file) and your program needs to compile and run without error in that format.
Explanation / Answer
#include<stdio.h>
#include<conio.h>
int a[10][10],visited[10],n,TOtal_Min_COst=0;
int min (int);
void input()
{
int i,j;
printf("Enter No. of Cities: ");
scanf("%d",&n);
printf(" Enter Cost Matrix ");
for(i=0;i < n;i++)
{
printf(" Enter Elements of Row # : %d ",i+1);
for( j=0;j < n;j++)
scanf("%d",&a[i][j]);
visited[i]=0;
}
printf(" The TOtal_Min_COst list is: ");
for( i=0;i < n;i++)
{
printf(" ");
for(j=0;j < n;j++)
printf(" %d",a[i][j]);
}
}
void mincost(int city)
{
int i,Nthcity;
visited[city]=1;
printf("%d -->",city+1);
Nthcity=min(city);
if(Nthcity==999)
{
Nthcity=0;//printf("hii");
printf("%d",Nthcity+1);
TOtal_Min_COst+=a[city][Nthcity];
return;
}
mincost(Nthcity);
}
int min(int c)
{
int i,ncNext_city=999;
int min=999,mi;
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];
mi=a[c][i];
ncNext_city=i;
}
}
if(min!=999)
TOtal_Min_COst+=mi;
return ncNext_city;
}
void display()
{
printf(" Minimum TOtal_Min_COst:");
printf("%d",TOtal_Min_COst);
}
int main()
{
//clrscr();
input();
printf(" The Path is: ");
mincost(0);
display();
return 0;
}