-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsales_person.c
153 lines (134 loc) · 3.83 KB
/
sales_person.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<stdio.h>
int a[10][10],n,visit[10];
int cost_opt=0,cost_apr=0;
int least_apr(int c);
int least_opt(int c);
void mincost_opt(int city)
{
int i,ncity;
visit[city]=1;
printf("%d-->",city);
ncity=least_opt(city);
if(ncity==999)
{
ncity=1;
printf("%d",ncity);
cost_opt+=a[city][ncity];
return;
}
mincost_opt(ncity);
}
void mincost_apr(int city)
{
int i,ncity;
visit[city]=1;
printf("%d-->",city);
ncity=least_apr(city);
if(ncity==999)
{
ncity=1;
printf("%d",ncity);
cost_apr+=a[city][ncity];
return;
}
mincost_apr(ncity);
}
int least_opt(int c)
{
int i,nc=999;
int min=999,kmin=999;
for(i=1;i<=n;i++)
{
if((a[c][i]!=0)&&(visit[i]==0))
if(a[c][i]<min)
{
min=a[i][1]+a[c][i];
kmin=a[c][i];
nc=i;
}
}
if(min!=999)
cost_opt+=kmin;
return nc;
}
int least_apr(int c)
{
int i,nc=999;
int min=999,kmin=999;
for(i=1;i<=n;i++)
{
if((a[c][i]!=0)&&(visit[i]==0))
if(a[c][i]<kmin)
{
min=a[i][1]+a[c][i];
kmin=a[c][i];
nc=i;
}
}
if(min!=999)
cost_apr+=kmin;
return nc;
}
void main()
{
int i,j;
printf("Enter No. of cities:\n");
scanf("%d",&n);
printf("Enter the cost matrix\n");
for(i=1;i<=n;i++)
{
printf("Enter elements of row:%d\n",i );
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
visit[i]=0;
}
printf("The cost list is \n");
for(i=1;i<=n;i++)
{
printf("\n\n");
for(j=1;j<=n;j++)
printf("\t%d",a[i][j]);
}
printf("\n\n Optimal Solution :\n");
printf("\n The path is :\n");
mincost_opt(1);
printf("\n Minimum cost:");
printf("%d",cost_opt);
printf("\n\n Approximated Solution :\n");
for(i=1;i<=n;i++)
visit[i]=0;
printf("\n The path is :\n");
mincost_apr(1);
printf("\nMinimum cost:");
printf("%d",cost_apr);
printf("\n\nError in approximation is approximated solution/optimal solution=%f \n", (float)cost_apr/cost_opt);
}
/*
Input
Enter No. of cities:
4
Enter the cost matrix
Enter elements of row:1
0 1 3 6
Enter elements of row:2
1 0 2 3
Enter elements of row:3
3 2 0 1
Enter elements of row:4
6 3 1 0
The cost list is
0 1 3 6
1 0 2 3
3 2 0 1
6 3 1 0
Output
Optimal Solution :
The path is :
1-->2-->4-->3-->1
Minimum cost:8
Approximated Solution :
The path is :
1-->2-->3-->4-->1
Minimum cost:10
Error in approximation is approximated solution/optimal solution=1.250000
*/