旅行商问题的近似算法之最近邻法(Nearest Neighbor) C语言实现

本文主要是介绍旅行商问题的近似算法之最近邻法(Nearest Neighbor) C语言实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

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

  5*/

  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  /* 最大城市数量 */

 14struct point{  /* 容纳城市的构造体*/
 double x;
 double y;
 17};

 19struct point city[MAX_CITY_NUM];  /* 都市坐标 */
 20int city_num;  /*城市数量 */
 21int tour[MAX_CITY_NUM];  /* 巡回路的顺序 */

 24double distance(int i, int j);  /* 计算距离函数 */
 25void nearest_neighbor(int start_city);


 29int 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);
 90}


 94double 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));
101}

104/* Nearest Neighbor法 */
105void 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;
 }
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

就读于日本关西大学

环境都市工学专攻

这篇关于旅行商问题的近似算法之最近邻法(Nearest Neighbor) C语言实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！