旅行商问题的近似算法之最近邻法(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)。

/* 
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

就读于日本关西大学

环境都市工学专攻

原文发布于微信公众号 - 程序猿声(ProgramDream)

原文发表时间:2019-07-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券