TSPLIB数据集简介与与C语言读取

上一个博客,我已经对贪心算法解决TSP问题进行了浅显的介绍。在这个博客中,我将具体介绍如何使用TSPLib对贪心算法的效果进行评价。同时为了提高代码的易读性,对函数接口进行了重新设计。

直观上只需检查算法的输出结果中,每一个城市出现且出现一次,该结果既是TSP问题的可行解,说明算法正确地求解了问题实例。

如果实例额度最优解已知(问题规模小或者已被成功求解),利用统计方法对若干问题实例的算法结果与最优解进行对比分析,即可对其进行效果评价。

对于较大规模的问题实例,其最优解往往是未知的,因此,算法的效果评价只能借助于与前人算法结果的比较。

这里因为我们从海德堡大学官方(见参考资料)给出的TSPLib和目前的最优解,因此我们采用TSPLib来对贪心算法的效果进行评价。

  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
前面的字符串表示数据集名称。
后面的数字表示目前给出的最优解距离。
a280 : 2579
ali535 : 202339
att48 : 10628
att532 : 27686
bayg29 : 1610
bays29 : 2020
berlin52 : 7542
bier127 : 118282
brazil58 : 25395
brd14051 : 469385
brg180 : 1950
burma14 : 3323
ch130 : 6110
ch150 : 6528
d198 : 15780
d493 : 35002
d657 : 48912
d1291 : 50801
d1655 : 62128
d2103 : 80450
d15112 : 1573084
d18512 : 645238
dantzig42 : 699
dsj1000 : 18659688 (EUC_2D)
dsj1000 : 18660188 (CEIL_2D)
eil51 : 426
eil76 : 538
eil101 : 629
fl417 : 11861
fl1400 : 20127
fl1577 : 22249
fl3795 : 28772
fnl4461 : 182566
fri26 : 937
gil262 : 2378
gr17 : 2085
gr21 : 2707
gr24 : 1272
gr48 : 5046
gr96 : 55209
gr120 : 6942
gr137 : 69853
gr202 : 40160
gr229 : 134602
gr431 : 171414
gr666 : 294358
hk48 : 11461
kroA100 : 21282
kroB100 : 22141
kroC100 : 20749
kroD100 : 21294
kroE100 : 22068
kroA150 : 26524
kroB150 : 26130
kroA200 : 29368
kroB200 : 29437
lin105 : 14379
lin318 : 42029
linhp318 : 41345
nrw1379 : 56638
p654 : 34643
pa561 : 2763
pcb442 : 50778
pcb1173 : 56892
pcb3038 : 137694
pla7397 : 23260728
pla33810 : 66048945
pla85900 : 142382641
pr76 : 108159
pr107 : 44303
pr124 : 59030
pr136 : 96772
pr144 : 58537
pr152 : 73682
pr226 : 80369
pr264 : 49135
pr299 : 48191
pr439 : 107217
pr1002 : 259045
pr2392 : 378032
rat99 : 1211
rat195 : 2323
rat575 : 6773
rat783 : 8806
rd100 : 7910
rd400 : 15281
rl1304 : 252948
rl1323 : 270199
rl1889 : 316536
rl5915 : 565530
rl5934 : 556045
rl11849 : 923288
si175 : 21407
si535 : 48450
si1032 : 92650
st70 : 675
swiss42 : 1273
ts225 : 126643
tsp225 : 3916
u159 : 42080
u574 : 36905
u724 : 41910
u1060 : 224094
u1432 : 152970
u1817 : 57201
u2152 : 64253
u2319 : 234256
ulysses16 : 6859
ulysses22 : 7013
usa13509 : 19982859
vm1084 : 239297
vm1748 : 336556

代码函数介绍:

 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
/**
 *打印访问顺序
 * @param S  已经访问过的城市数组
 * @param n  城市个数
 */
void PathPrint(int S[],int n)
  
/**
 * 打印访问路径的总路程
 * @param cityNum 城市数量
 * @param S 城市访问顺序数组
 * @param D 给一个城市距离矩阵
 * @return
 */
int sumDistance(int cityNum , int S[cityNum],int D[][cityNum])
  
 /**
 *对从所有未访问过的城市中查找距离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) 
  
/**
 * 贪婪算法主体(和上一节写的基本一致)
 * @param n 城市个数
 * @param D 城市之间的距离
 * @param S 已经访问过的城市数组 因为从索引1开始进行记录n个城市 所以n+1
 * @return
 */
int Tsp(int n,int D[][n],int S[n+1])
  
/**
 *
 * @param cityNum 城市数量
 * @param coordinate 城市到欧几里得坐标 注意这里使用的是欧几里得距离 如果数据集中的不是欧几里得距离要先转化为欧几里得距离
 * @param D 作为返回参数传递 返回城市之间到距离矩阵
 */
void Distance(int cityNum,int coordinate[cityNum][2],int D[cityNum][cityNum]) 
  

/**
 * 读取城市数量 并返回距离矩阵
 * @param cityNum 城市数量
 * @param D 要返回的城市距离矩阵
 * @param a 要读取的tsplib名
 */
void Read_Coordinate(int cityNum, int D[cityNum][cityNum],char a[])
  
  /**
 * 读取最优路径
 * @param cityNum 城市数量 
 * @param a 表访问的数据集名
 * @param best_path 通过读取后的最优城市路径数组存储在best_path中
 */
void Read_opt_path(int cityNum,char a[],int best_path[cityNum+1])
  
  /**
 * 给出了具体的程序运行顺序(重点)
 */
 void test(int cityNum, char * a,char * b)
  
  //程序入口
  int main() 

代码实现:

  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;
}

最后得到的结果为:

1
2
3
4
5
贪心算法给出的距离为:12861
城市1----->城市9----->城市38----->城市31----->城市44----->城市18----->城市7----->城市28----->城市36----->城市30----->城市6----->城市37----->城市19----->城市27----->城市43----->城市17----->城市33----->城市46----->城市15----->城市12----->城市11----->城市23----->城市14----->城市25----->城市13----->城市21----->城市47----->城市20----->城市40----->城市3----->城市22----->城市16----->城市41----->城市34----->城市29----->城市5----->城市48----->城市39----->城市32----->城市24----->城市10----->城市42----->城市26----->城市4----->城市35----->城市45----->城市2----->城市8----->城市1
官方给的当前最优解为:10628
城市1----->城市8----->城市38----->城市31----->城市44----->城市18----->城市7----->城市28----->城市6----->城市37----->城市19----->城市27----->城市17----->城市43----->城市30----->城市36----->城市46----->城市33----->城市20----->城市47----->城市21----->城市32----->城市39----->城市48----->城市5----->城市42----->城市24----->城市10----->城市45----->城市35----->城市4----->城市26----->城市2----->城市29----->城市34----->城市41----->城市16----->城市22----->城市3----->城市23----->城市14----->城市25----->城市13----->城市11----->城市12----->城市15----->城市40----->城市9----->城市1
官方/贪心算法的距离比为:1.210105

1.使用SOM神经网络对TSP问题进行优化

2.对城市路径进行绘图比较

海德堡大学官方数据集:

http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/

TSPLIB数据文件的读取:

https://blog.csdn.net/shuangmu_chenglin/article/details/100902332