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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
/**
*打印访问顺序
* @param S 已经访问过的城市数组
* @param n 城市个数
*/
void PathPrint(int S[],int n)
{
int i;
printf("城市%d",S[1]);
for (i = 2; i <=n; i++) {
printf("----->城市%d",S[i]);
}
printf("----->城市%d\n",S[1]);
}
//打印访问路径的总路程
/**
*
* @param cityNum 城市数量
* @param S 城市访问顺序数组
* @param D 给一个城市距离矩阵
* @return
*/
int sumDistance(int cityNum , int S[cityNum],int D[][cityNum])
{
int i;
int sum = 0 ;
for (i = 2; i <=48 ; i++) {
sum +=D[S[i-1]-1][S[i]-1];
}
sum+=D[0][S[48]-1];
return sum;
}
/**
*从所有未访问过的城市中查找距离S[I-1]最近的城市j
* @param I 访问次数 0-I-1次表示已经访问过 S[I-1]表示目前所在位置 S[I]表示将要访问的地方
* @param S S数组表示已经访问过的地方
* @param n 表示地点个数
* @param D 表示两地点间的距离
* @param Dtemp 表示两城市间的最短距离
* @return
*/
int FindCity(int I, const int *S, int n,int D[][n],int *Dtemp)
{
//用来存储 K城市到当前城市S[I-1]的距离 初始化为一个大数
*Dtemp=1000000000;
//从第2个城市到第N个城市（最后一个城市）进行遍历 寻找未被访问过的最近城市
int K =2;
//用来存储第I次访问的城市代号
int j;
//从2到n个城市中查找一个没有被访问过且距离当前城市S[I-1]最近到城市
do {
//当我们拿到一个城市K的时候，我们不知道这个城市是否被访问过，所以通过下面这个循环来判断该城市是否被访问过
//使用L从第1个城市到到第I-1个城市进行遍历（目前走过的城市） 看城市K是否被访问过
int L =1;
do
{
//如果城市K已经是被访问过的城市 那就跳出循环，看K+1这个城市是否被访问过
if(S[L] == K)
{
break;
}
//如果K城市没被访问过 那就从S[L+1]中找K 一直找到L==I-1
L+=1;
} while (L<I);
//有两种情况为出循环
//如果是自然退出循环(即城市K没有被访问过） 那L==I
if(L==I)
{
//此时就要对城市K到S[I-1]进行记录
if((D[K-1][S[I-1]-1]) < *Dtemp)
{
j = K;
*Dtemp = D[K-1][S[I-1]-1];
}
}
K+=1;
} while (K<=n);
return j;
}
/**
* 贪婪算法主体
* @param n 城市个数
* @param D 城市之间的距离
* @param S 已经访问过的城市数组 因为从索引1开始进行记录n个城市 所以n+1
* @return
*/
int Tsp(int n,int D[][n],int S[n+1])
{
int Sum;
int I; //已经进行了I-1次访问 目前正在进行第I次访问
int Dtemp;
int j; //用来存储第I次访问的城市代号
//初始化
//初始化最终的访问距离为0
Sum = 0;
//表示城市1现在被访问过了
S[1]=1;
//开始进行访问
//表示进行第二次访问的城市
I = 2;
//如果第I次访问小于等于N 那么说明访问未完成
do {
j = FindCity(I,S,n,D,&Dtemp);
//找到距离我们目前城市最近的城市j后 旅行到城市j
S[I] = j;
//接下来对下一个城市进行访问
I+=1;
//将之前城市到j的距离加入sum中
Sum+=Dtemp;
} while (I<=n);
//如果走到来最后一个城市 那么就回到出发城市
Sum=Sum+D[1][j];
return Sum;
}
/**
*
* @param cityNum 城市数量
* @param coordinate 城市到欧几里得坐标
* @param D 作为返回参数传递 返回城市之间到距离矩阵
*/
void Distance(int cityNum,int coordinate[cityNum][2],int D[cityNum][cityNum]) {
//计算距离
int i;
//划分城市的横纵坐标 将横纵坐标分别存储到数组x和数组y中方便之后到计算
//存储横坐标
int x[cityNum];
//存储纵坐标
int y[cityNum];
int k;
for (k = 0; k < cityNum; k++) {
x[k] = coordinate[k][0];
}
int j;
for (j = 0; j < cityNum; j++) {
y[j] = coordinate[j][1];
}
//进行距离矩阵的计算
for (i = 0; i < cityNum - 1; i++) {
//对角线为0
D[i][i] = 0;
j=0;
for (j = i + 1; j < cityNum; j++) {
double rij = sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) / 10.0);
// 四舍五入，取整
int tij = (int) round(rij);
if (tij < rij) {
D[i][j] = tij + 1;
D[j][i] = D[i][j];
} else {
D[i][j] = tij;
D[j][i] = D[i][j];
}
}
}
D[cityNum - 1][cityNum - 1] = 0;
}
//读取城市数量 并返回距离矩阵
/**
*
* @param cityNum 城市数量
* @param D 要返回的城市距离矩阵
* @param a 要读取的tsplib名
*/
void Read_Coordinate(int cityNum, int D[cityNum][cityNum],char a[])
{
FILE* fp;
int coordinate[cityNum][2];
char str[100]; //暂存读取的字符串
int i = 1, j = 0, m = 0; //i控制从城市坐标文件第几行读取，j控制只读坐标值，不读城市编号,m为城市坐标赋值下标
//为了保证足够拼接
char p[200] = "/Users/ningxu/CLionProjects/CUDA/tsplib_data/";
strcat(p,a);
fp=fopen(p,"r");
while (i < 7)
{
fgets(str, 255, fp);
i++;
}
//printf("%s",str);
//如果遇到文件结尾返回1
while (!feof(fp))
{
fscanf(fp, "%s\n", str);
if (j % 3 == 1) {
coordinate[m][0] = atoi(str);
}
else if (j % 3 == 2) {
coordinate[m][1] = atoi(str);
m++;
}
j++;
}
fclose(fp);
//距离矩阵
Distance(cityNum,coordinate,D);
}
/**
* 读取最优路径
* @param cityNum 城市数量
* @param a 表访问的数据集名
* @param best_path 通过读取后的最优城市路径数组存储在best_path中
*/
void Read_opt_path(int cityNum,char a[],int best_path[cityNum+1])
{
//为了保证足够拼接
char p[200] = "/Users/ningxu/CLionProjects/CUDA/tsplib_data/";
strcat(p,a);
//因为我们设计的InfoPrint是从1号元素开始打印的 所以这里为了统一从索引1开始存储
FILE* fp;
char str[100]; //暂存读取的字符串
int i0 = 1, j0 = 0; //i0控制从最优路径文件第几行读取，j0为最优路径赋值下标
int i = 1, j = 0, m = 0; //i控制从城市坐标文件第几行读取，j控制只读坐标值，不读城市编号,m为城市坐标赋值下标
fp = fopen(p, "r");
while (i0 < 6)
{
fgets(str, 255, fp);
i0++;
}
while (!feof(fp) && j0 < cityNum)
{
fscanf(fp, "%s\n", str);
best_path[j0+1] = atoi(str);
j0++;
}
fclose(fp);
}
void test(int cityNum, char * a,char * b)
{
//声明一个城市距离矩阵 之后会通过Read_Coordinate（阅读城市的坐标计算出距离矩阵）计算出城市间的距离矩阵
int D[cityNum][cityNum];
//声明一个路径数组 用来记录贪心算法给出的局部最优路径
int my_path[cityNum+1];
//声明一个最佳路径数组 用来记录目前官方给的最优路径
int best_path[cityNum+1];
//读取坐标文件 获取距离矩阵
Read_Coordinate(cityNum,D,"att48.tsp");
//使用贪心算法进行路径规划
Tsp(cityNum,D,my_path);
//给出贪心算法的路径
printf("贪心算法给出的距离为：%d\n",sumDistance(cityNum,my_path,D)) ;
PathPrint(my_path,cityNum);
//读取官方给定的最优路径 记录最优路径到数组
Read_opt_path(cityNum,"att48.opt.tour",best_path);
//给出最优路径的总距离
sumDistance(cityNum,best_path,D);
printf("官方给的当前最优解为：%d\n",sumDistance(cityNum,best_path,D)) ;
PathPrint(best_path,cityNum);
float radio = (float)(sumDistance(cityNum,my_path,D))/(float)(sumDistance(cityNum,best_path,D));
printf("官方/贪心算法的距离比为：%f",radio);
}
int main() {
//输入的城市个数
int cityNum = 48;
//要读取的文件
test(cityNum,"berlin52.tsp","berlin52.opt.tour");
return 0;
}
|