monituihuo3.cpp

模拟退火解巡视路线（Tsp）

#include<stdio.h>
#include<conio.h>
#include "iostream.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define MAX 10000.0
#define N 53
#define K 1000;



float d[N][N];
unsigned char P[N][N][15];
int num[N][N];


double w_random()
{
 int a;
 double r;

 a=rand()%32767;
 r=(a+0.00)/32767.00;

 return r;

}

int w_randN(int seed)
{
 return rand()%seed+1;

}

void  main()
{

FILE *p=fopen("E:\\共享资料库\\distance.txt","r");
int v1,v2,dump;
float dis;
int n=N;
int i,j,k,l,m;
float maxf,minf,fu,fl,t0,t,df,f0,f1,ff0,ff1;
int   aa[N+1],i1,i2,at,at1,g,gg,sign0;
float fa=0.995,e=0.01;
time_t  tt0;
tt0=time(0);
srand(int((tt0%10000)*7.89));
for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    {
     if(i==j)  { d[i][j]=0.0;num[i][j]=0; }
     else
	  {
	   d[i][j]=MAX+1.0;
	  }
    }
for(i=0;i<91;i++)
 {
  fscanf(p,"%c%d,%d,%f%c",&dump,&v1,&v2,&dis,&dump);
  fscanf(p,"%c%d,%d,%f%c",&dump,&v1,&v2,&dis,&dump);
  d[v1-1][v2-1]=d[v2-1][v1-1]=dis;
  
 }
fclose(p);

for(k=0;k<n;k++)
  for(i=0;i<n;i++)
     for(j=0;j<n;j++)
       if(d[i][k]+d[k][j]<d[i][j])
	  {
	   d[i][j]=d[i][k]+d[k][j];
	   
	  }
maxf=0;minf=0;
for(i=0;i<n;i++)
{fu=0;fl=MAX;
	for(j=0;j<n;j++)
		if(j!=i)
		{if(d[i][j]>fu) fu=d[i][j];
		 if(d[i][j]<fl) fl=d[i][j];
		}
 maxf=maxf+fu;
 minf=minf+fl;
}
t0=(maxf-minf)*K;
cout<<maxf<<" ,"<<minf<<","<<t0<<endl;
t=t0;
f0=0;
aa[0]=49;
for(i=1;i<N;i++)
{ if(i==49)aa[i]=0;
	else      aa[i]=i;
  f0=f0+d[aa[i]][aa[i-1]];
}
aa[i]=49;
f0=f0+d[i-1][49];
ff0=f0;g=0;gg=0;f1=f0;ff1=ff0;
while(t>e)
{for(i=0;i<2*n*n;i++)
{i1=w_randN(n-1);
i2=w_randN(n-1);
 if(i2==(i1+1)||i1>=i2)continue;
 else if(i1==i2-2) {df=d[aa[i1-1]][aa[i2]]+d[aa[i1]][aa[i2+1]]-(d[aa[i1-1]][aa[i1]]+d[aa[i2]][aa[i2+1]]);
					if(df<0) {at=aa[i1];aa[i1]=aa[i2];aa[i2]=at;f0=f0+df;if(f0<ff0) ff0=f0;}
					else if(exp(-1*df/t)>w_random()) {at=aa[i1];aa[i1]=aa[i2];aa[i2]=at;f0=f0+df;}
					}
	  else  if(i1==i2-3){df=d[aa[i1-1]][aa[i2]]+d[aa[i2-1]][aa[i1+1]]+d[aa[i2-1]][aa[i1+1]]+d[aa[i1]][aa[i2+1]]-(d[aa[i1-1]][aa[i1]]+d[aa[i1+1]][aa[i1+2]]+d[aa[i2-2]][aa[i2-1]]+d[aa[i2]][aa[i2+1]]);
						if(df<0) {at=aa[i1];at1=aa[i1+1];sign0=1;
								  aa[i1]=aa[i2];aa[i1+1]=aa[i2-1];aa[i2]=at;aa[i2-1]=at1;f0=f0+df;}
						else if(exp(-1*df/t)>w_random())
								{at=aa[i1];at1=aa[i1+1];
								 aa[i1]=aa[i2];aa[i1+1]=aa[i2-1];aa[i2]=at;aa[i2-1]=at1;f0=f0+df;
								}
						}
			else if(i1<i2-3)  {df=d[aa[i1-1]][aa[i2]]+d[aa[i2-1]][aa[i1+2]]+d[aa[i2-2]][aa[i1+1]]+d[aa[i1]][aa[i2+1]]-(d[aa[i1-1]][aa[i1]]+d[aa[i1+1]][aa[i1+2]]+d[aa[i2-2]][aa[i2-1]]+d[aa[i2]][aa[i2+1]]);
								if(df<0) {at=aa[i1];at1=aa[i1+1];sign0=1;
											aa[i1]=aa[i2];aa[i1+1]=aa[i2-1];aa[i2]=at;aa[i2-1]=at1;f0=f0+df;}
								else if(exp(-1*df/t)>w_random())
										{at=aa[i1];at1=aa[i1+1];
										aa[i1]=aa[i2];aa[i1+1]=aa[i2-1];aa[i2]=at;aa[i2-1]=at1;f0=f0+df;
										}
								}
 }
cout<<f0<<" ";
t=fa*t;
//if(f0<=600) {cout<<t;getch();}
}
cout<<endl<<ff0;

}