#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;
}
评论0