tsp_orc.c

TSP算法 1.C语言TSP算法 2.2-OPT

/* 弰夞僙乕儖僗儅儞栤戣傪夝偔嬊強扵嶕朄偵傛傞嬤帡
傾儖僑儕僘儉乮2-OPT偍傛傃OR-OPT嬤朤) */

#include <stdio.h>
#include <stdlib.h> 
#include <math.h>
#define N 600         /* 抧揰悢偺嵟戝僒僀僘 */
#define ZERO 0.0001   /* 嫋梕岆嵎暆 */
#define SEED 14       /* 棎悢偺庬 */ 
struct point          /* 峔憿懱p偺掕媊 */
{
 float x;
 float y;
};
int n;                /* 奜晹曄悢丗揰偺屄悢 */
struct point p[N];    /* p[i].x偲p[i].y偼揰i偺嵗昗 */

/* 娭悢偺愰尵 */
float initial(int *x);
float local(int *init, float lginit, int *lopt);
float length(int i, int j, int *x);
void printtour(int *x, float length);
int rand_from(int min, int max);

main()
/* TSP嬊強扵嶕朄偺僥僗僩僾儘僌儔儉 */
{
 int i, init[N], lopt[N];
 float initlg, bestlg;
 FILE *file;
 file=fopen("locdata1", "r");   /* 擖椡僨乕僞偺撉崬 */
 fscanf(file, "%d", &n);
 for(i=0; i<n; i++)
 {
  fscanf(file, "%f", &p[i].x);
  fscanf(file, "%f", &p[i].y);
 }
 printf("n = %d\n", n);
 printf("point i       x[i]       y[i] \n");
 for(i=0; i<n; i++) 
  printf("%3d        %f,  %f\n", i, p[i].x, p[i].y);
 srand(SEED);
 initlg=initial(init);          /* 弶婜弰夞楬偺惗惉 */
 printf("initial tour\n");
 printtour(init, initlg);
 bestlg=local(init, initlg, lopt);  /* 嬊強扵嶕 */
 printf("local optimal tour\n");    /* 寢壥偺弌椡 */
 printtour(lopt, bestlg);
}

float initial(int *x)
/* 抧揰悢n偺弶婜弰夞楬傪x偵嶌惉丄偦偺挿偝偑弌椡偝傟傞 */
{
 int i, j, r, test[N];   /* test[i]偼抧揰i偺棙梡僼儔僌 */
 float lg;
 for(i=0; i<n; i++) test[i]=0;
 j=0;
 for(i=0; i<n; i++)
 {
  r=rand_from(0, n-i-1);  /* 抧揰j偐傜r屄栚偺嬻偒抧揰傪x[i]偲偡傞 */
  while(test[j]==1) j=(j+1)%n;
  while(r>0)
  {
   r=r-1; j=(j+1)%n;
   while(test[j]==1) j=(j+1)%n;
  }
  test[j]=1; x[i]=j;
 } 
 lg=0.0;
 for(i=0; i<n; i++) lg=lg+length(i, i+1, x);  /* 弰夞楬偺挿偝 */
 return(lg);
}

float local(int *init, float initlg, int *lopt)
/* 弰夞楬init傪弶婜夝乮偦偺挿偝initlg乯偲偟偰丄2-OPT偍傛傃OR-OPT嬤朤偵
傛傞嬊強扵嶕傪揔梡偟丄嬊強嵟揔夝lopt偺弰夞楬挿傪弌椡 */
{
 int i, i0, j, k, h, temp, tm[3];
 float lg, lgtemp, lg0, lg1;
 for(i=0; i<n; i++) lopt[i]=init[i];
 lg=initlg;
 i0=0;
 RESTART:                             /* 嬤朤扵嶕偺奐巒 */
 for(i=i0; i<i0+n; i++)               /* 2-OPT嬤朤偺扵嶕 */
 {
  for(j=i+2; j<i+n-1; j++)            /* lgtemp偼挿偝偺憹暘 */
  {
   lgtemp=length(i, j, lopt)+length(i+1, j+1, lopt)
          -length(i, i+1, lopt)-length(j, j+1, lopt);
   if(lgtemp<-ZERO)                   /* 夵椙夝偺敪尒 */
   {
    lg=lg+lgtemp;
    for(k=0; k<(j-i)/2; k++)          /* 夵椙夝偺峔惉 */
    {
     temp=lopt[(i+1+k)%n]; lopt[(i+1+k)%n]=lopt[(j-k)%n]; 
     lopt[(j-k)%n]=temp;
    }
    printf("improved solution by 2-OPT\n");
    goto IMPROVED;
   }
  } 
 } 
 for(i=i0; i<i0+n; i++)             /* Or-OPT嬤朤偺扵嶕 */ 
 {
  for(k=i+1; k<=i+3; k++)
  {
   for(j=k+1; j<i+n-1; j++)         /* lgtemp偼挿偝偺憹暘 */
   {
    lg0=length(i, i+1, lopt)+length(j, j+1,lopt)+length(k, k+1, lopt);
    lg1=length(i, k+1, lopt)+length(j, k, lopt)+length(i+1, j+1,lopt);
    lgtemp=lg1-lg0;
    if(lgtemp<-ZERO)                /* 夵椙夝偺敪尒 */
    {
     lg=lg+lgtemp;                  /* 夵椙夝偺峔惉 */
     for(h=i+1; h<=k; h++) tm[h-i-1]=lopt[h%n];
     for(h=k+1; h<=j; h++) lopt[(h-k+i)%n]=lopt[h%n];
     for(h=0; h<k-i; h++) lopt[(j-k+i+1+h)%n]=tm[k-i-1-h];
     printf("improved solution by Or-OPT\n");
     goto IMPROVED;
    }
    if(k==i+1) continue;
    lg1=length(i, k+1, lopt)+length(j, i+1, lopt) /* 媡曽岦偺憓擖 */
        +length(k, j+1, lopt);
    lgtemp=lg1-lg0;
    if(lgtemp<-ZERO)                /* 夵椙夝偺敪尒 */
    {
     lg=lg+lgtemp;                  /* 夵椙夝偺峔惉 */
     for(h=i+1; h<=k; h++) tm[h-i-1]=lopt[h%n];
     for(h=k+1; h<=j; h++) lopt[(h-k+i)%n]=lopt[h%n];
     for(h=0; h<k-i; h++) lopt[(j-h)%n]=tm[k-i-1-h];
     printf("improved solution by Or-OPT\n");
     goto IMPROVED;
    }
   }
  }
 }
 return(lg);                     /* 嬊強扵嶕廔椆 */
 IMPROVED:                       /* 巄掕夝偺峏怴丗師偺嬤朤扵嶕傊 */
 printtour(lopt, lg); i0=(i+1)%n; 
 goto RESTART;
}

float length(int i, int j, int *x)
/* p[x[i%n]]偲p[x[j%n]]偺儐乕僋儕僢僪嫍棧 */
{
 return(sqrt(pow(p[x[i%n]].x-p[x[j%n]].x, 2)
    +pow(p[x[i%n]].y-p[x[j%n]].y, 2)));
}


void printtour(int *x, float lg)
/* 弰夞楬x偲偦偺挿偝lg傪弌椡 */
{
 int i;
 printf("tour = (");
 for(i=0; i<n; i++) printf("%d ", x[i]); printf(")\n");
 printf("length = %f\n", lg);
}

int rand_from(int min, int max)
/* 嬫娫[min, max]偐傜儔儞僟儉偵惍悢傪慖傇 */
/* rand偼0偐傜RAND_MAX傑偱偺棎惍悢傪惗惉偡傞昗弨娭悢 */
{
 return((int)(((double)rand()/((unsigned)RAND_MAX+1))
   *(max-min+1))+min);
}