Trend Posts
Author
View LUQMAN's profile
Showing posts with label approximation. Show all posts
Showing posts with label approximation. Show all posts
Monday, July 21, 2014
/*Implement any scheme to find the solution for the TravelingSalesperson in the approximation method*/
#include<stdio.h>
void tspaprx(int);
int n,cost[100][100],s,count=0,mincost,visited[100],u,i,j,min;
void main()
{
printf("\nEnter the number of nodes\n");
scanf("%d",&n);
printf("\nEnter the cost matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
printf("\nEntered cost matrix is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",cost[i][j]);
printf("\n");
}
printf("\nThe approximate tour is:\n");
tspaprx(1);
}
void tspaprx(int s)
{
visited[s]=1;
count++;
printf("%d->",s);
if(count==n)
{
printf("1");
mincost+=cost[s][1];
printf("\nThe minimum tour cost is %d",mincost);
return;
}
min=999;
for(i=1;i<=n;i++)
{
if(cost[s][i]<min && !visited[i])
{
min=cost[s][i];
u=i;
}
}
mincost+=min;
tspaprx(u);
}
Subscribe to:
Posts (Atom)