目录
TSP的近似算法
01
对于近似算法，我们一般可分为两类：
一，构造法。二，改善法。
TSP也不例外。这里我们做一下分类：
构造法
1. 最近邻法
2. 最近插入法
3. Greedy法
4. ......
改善法
1. 局部搜索法 2-opt，3-opt
2. SA法
3. Tabu Search法
4. 遗传算法
5. ......
另外，实际设计算法时，有一个常用的Idea就是我们用构筑法生成初始解放到改善法里去Improve。
最近邻法
02
今天，我们先来说说TSP的最近邻法，这是一个最简单的TSP启发式算法。如图
图中，绿色点为出发城市。
1. 首先，我们选择适当的城市作为出发城市。
2. 其次，从没有访问过的城市当中，选择离当前城市最近的城市，移动
3. 最后，如果所有的城市都访问了，那么回到出发城市
是不是很简单啊！！！！
最近邻法代码实现
03
我们用C语言编写，用benchmark作为测试数据(berlin52.dat)。
1/*
2TSP Nearest Neighbor法
3Code reference: Prof.Umetani Shunji
4
5*/
6
7#include <stdlib.h>
8#include <stdio.h>
9#include <math.h>
10#include <time.h>
11#include <float.h>
12#define MAX_CITY_NUM 3000 /* 最大城市数量 */
13
14struct point{ /* 容纳城市的构造体*/
15 double x;
16 double y;
17};
18
19struct point city[MAX_CITY_NUM]; /* 都市坐标 */
20int city_num; /*城市数量 */
21int tour[MAX_CITY_NUM]; /* 巡回路的顺序 */
22
23
24double distance(int i, int j); /* 计算距离函数 */
25void nearest_neighbor(int start_city);
26
27
28
29int main(int argc, char *argv[]){
30
31 FILE *input_file, *output_file;
32 double length;
33 int i;
34 double start_time, search_time;
35
36
37 if(argc <= 1){
38 fprintf(stderr,"Please input the name of data file!\n");
39 exit(1);
40 }
41
42 /* 读取数据 */
43 input_file = fopen(argv[1], "r");
44 fscanf(input_file,"%d", &city_num);
45 for(i = 0; i < city_num; i++){
46 fscanf(input_file,"%lf %lf",&(city[i].x),&(city[i].y));
47 }
48 fclose(input_file);
49
50 /* 显示读取数据*/
51 printf("city_num= %d\n",city_num);
52 for(i = 0; i < city_num; i++){
53 printf("%4d\t%f\t%f\n",i,city[i].x,city[i].y);
54 }
55
56 /* 开始时间 */
57 start_time = (double)clock()/CLOCKS_PER_SEC;
58
59 /* Nearest Neighbor法 */
60 nearest_neighbor(0);
61
62 /*结束时间*/
63 search_time = (double)clock()/CLOCKS_PER_SEC - start_time;
64
65 /* 总距离的计算 */
66 length = 0.0;
67 for(i = 0; i < city_num; i++){
68 length += distance(tour[i % city_num], tour[(i+1) % city_num]);
69 }
70 /* 城市数据的输出 */
71 output_file = fopen("result.dat","w");
72 fprintf(output_file,"%d\n",city_num);
73 for(i = 0; i < city_num; i++){
74 fprintf(output_file,"%f %f\n",city[i].x,city[i].y);
75 }
76
77 /* 巡回路的输出 */
78 length = 0.0;
79 printf("\nTour: ");
80 for(i = 0; i < city_num; i++){
81 fprintf(output_file,"%d\n",tour[i]);
82 printf("%d ",tour[i]);
83 length += distance(tour[i],tour[(i+1) % city_num]);
84 }
85 fclose(output_file);
86 printf("\nLength: %f\n",length);
87 printf("CPU Time: %f\n",search_time);
88
89 return(0);
90}
91
92
93
94double distance(int i, int j){
95
96 double xd, yd;
97
98 xd = city[i].x - city[j].x;
99 yd = city[i].y - city[j].y;
100 return((int)(sqrt(xd * xd + yd * yd) + 0.5));
101}
102
103
104/* Nearest Neighbor法 */
105void nearest_neighbor(int start_city){
106
107 double min_dist;
108 int arg_min_dist, temp;
109 int i,j;
110
111 /* 初始化巡回路 */
112 tour[0] = start_city;
113 j = 1;
114 for(i = 0; i < city_num; i++){
115 if(i != start_city){
116 tour[j] = i;
117 j++;
118
119 }
120 }
121
122
123 for(i = 1; i < city_num-1; i++){
124
125 /* 寻找距离都市tour[i-1]最近没有访问的城市 */
126 min_dist = FLT_MAX;
127 arg_min_dist = -1;
128 for(j = i; j < city_num; j++){
129 if(distance(tour[i-1],tour[j]) < min_dist){
130 min_dist = distance(tour[i-1],tour[j]);
131 arg_min_dist = j;
132 }
133 }
134
135 /* 城市tour[i]と城市tour[arg_min_dist]交换 */
136 temp = tour[i];
137 tour[i] = tour[arg_min_dist];
138 tour[arg_min_dist] = temp;
139 }
140}
数据
152
2565.0 575.0
325.0 185.0
4345.0 750.0
5945.0 685.0
6845.0 655.0
7880.0 660.0
825.0 230.0
9525.0 1000.0
10580.0 1175.0
11650.0 1130.0
121605.0 620.0
131220.0 580.0
141465.0 200.0
151530.0 5.0
16845.0 680.0
17725.0 370.0
18145.0 665.0
19415.0 635.0
20510.0 875.0
21560.0 365.0
22300.0 465.0
23520.0 585.0
24480.0 415.0
25835.0 625.0
26975.0 580.0
271215.0 245.0
281320.0 315.0
291250.0 400.0
30660.0 180.0
31410.0 250.0
32420.0 555.0
33575.0 665.0
341150.0 1160.0
35700.0 580.0
36685.0 595.0
37685.0 610.0
38770.0 610.0
39795.0 645.0
40720.0 635.0
41760.0 650.0
42475.0 960.0
4395.0 260.0
44875.0 920.0
45700.0 500.0
46555.0 815.0
47830.0 485.0
481170.0 65.0
49830.0 610.0
50605.0 625.0
51595.0 360.0
521340.0 725.0
531740.0 245.0
保存代码为tsp_nn.c，数据为berlin52.dat，执行以下命令
1gcc -o tsp_nn tsp_nn.c
2tsp_nn.exe berlin52.dat
结果
如果有什么疑问或者建议，可以给我发邮件。
➡ zhaoyou728@outlook.com
转载声明：
本文转载自知乎专栏
作者 | 赵友 24岁
邮箱 | zhaoyou728@outlook.com
就读于日本关西大学
环境都市工学专攻