目录
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)。
/*
TSP Nearest Neighbor法
Code reference: Prof.Umetani Shunji
*/
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <float.h>
#define MAX_CITY_NUM 3000 /* 最大城市数量 */
struct point{ /* 容纳城市的构造体*/
double x;
double y;
};
struct point city[MAX_CITY_NUM]; /* 都市坐标 */
int city_num; /*城市数量 */
int tour[MAX_CITY_NUM]; /* 巡回路的顺序 */
double distance(int i, int j); /* 计算距离函数 */
void nearest_neighbor(int start_city);
int main(int argc, char *argv[]){
FILE *input_file, *output_file;
double length;
int i;
double start_time, search_time;
if(argc <= 1){
fprintf(stderr,"Please input the name of data file!\n");
exit(1);
}
/* 读取数据 */
input_file = fopen(argv[1], "r");
fscanf(input_file,"%d", &city_num);
for(i = 0; i < city_num; i++){
fscanf(input_file,"%lf %lf",&(city[i].x),&(city[i].y));
}
fclose(input_file);
/* 显示读取数据*/
printf("city_num= %d\n",city_num);
for(i = 0; i < city_num; i++){
printf("%4d\t%f\t%f\n",i,city[i].x,city[i].y);
}
/* 开始时间 */
start_time = (double)clock()/CLOCKS_PER_SEC;
/* Nearest Neighbor法 */
nearest_neighbor(0);
/*结束时间*/
search_time = (double)clock()/CLOCKS_PER_SEC - start_time;
/* 总距离的计算 */
length = 0.0;
for(i = 0; i < city_num; i++){
length += distance(tour[i % city_num], tour[(i+1) % city_num]);
}
/* 城市数据的输出 */
output_file = fopen("result.dat","w");
fprintf(output_file,"%d\n",city_num);
for(i = 0; i < city_num; i++){
fprintf(output_file,"%f %f\n",city[i].x,city[i].y);
}
/* 巡回路的输出 */
length = 0.0;
printf("\nTour: ");
for(i = 0; i < city_num; i++){
fprintf(output_file,"%d\n",tour[i]);
printf("%d ",tour[i]);
length += distance(tour[i],tour[(i+1) % city_num]);
}
fclose(output_file);
printf("\nLength: %f\n",length);
printf("CPU Time: %f\n",search_time);
return(0);
}
double distance(int i, int j){
double xd, yd;
xd = city[i].x - city[j].x;
yd = city[i].y - city[j].y;
return((int)(sqrt(xd * xd + yd * yd) + 0.5));
}
/* Nearest Neighbor法 */
void nearest_neighbor(int start_city){
double min_dist;
int arg_min_dist, temp;
int i,j;
/* 初始化巡回路 */
tour[0] = start_city;
j = 1;
for(i = 0; i < city_num; i++){
if(i != start_city){
tour[j] = i;
j++;
}
}
for(i = 1; i < city_num-1; i++){
/* 寻找距离都市tour[i-1]最近没有访问的城市 */
min_dist = FLT_MAX;
arg_min_dist = -1;
for(j = i; j < city_num; j++){
if(distance(tour[i-1],tour[j]) < min_dist){
min_dist = distance(tour[i-1],tour[j]);
arg_min_dist = j;
}
}
/* 城市tour[i]と城市tour[arg_min_dist]交换 */
temp = tour[i];
tour[i] = tour[arg_min_dist];
tour[arg_min_dist] = temp;
}
}
数据
52
565.0 575.0
25.0 185.0
345.0 750.0
945.0 685.0
845.0 655.0
880.0 660.0
25.0 230.0
525.0 1000.0
580.0 1175.0
650.0 1130.0
1605.0 620.0
1220.0 580.0
1465.0 200.0
1530.0 5.0
845.0 680.0
725.0 370.0
145.0 665.0
415.0 635.0
510.0 875.0
560.0 365.0
300.0 465.0
520.0 585.0
480.0 415.0
835.0 625.0
975.0 580.0
1215.0 245.0
1320.0 315.0
1250.0 400.0
660.0 180.0
410.0 250.0
420.0 555.0
575.0 665.0
1150.0 1160.0
700.0 580.0
685.0 595.0
685.0 610.0
770.0 610.0
795.0 645.0
720.0 635.0
760.0 650.0
475.0 960.0
95.0 260.0
875.0 920.0
700.0 500.0
555.0 815.0
830.0 485.0
1170.0 65.0
830.0 610.0
605.0 625.0
595.0 360.0
1340.0 725.0
1740.0 245.0
保存代码为tsp_nn.c,数据为berlin52.dat,执行以下命令
gcc -o tsp_nn tsp_nn.c
tsp_nn.exe berlin52.dat
结果
如果有什么疑问或者建议,可以给我发邮件。
➡ zhaoyou728@outlook.com
转载声明:
本文转载自知乎专栏
作者 | 赵友 24岁
邮箱 | zhaoyou728@outlook.com
就读于日本关西大学
环境都市工学专攻