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

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

gcc -o tsp_nn tsp_nn.c
tsp_nn.exe berlin52.dat