MTSP.rar_MTSP_graph theory_mtsp问题 Java_商旅问题模型_多商旅问题

#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; }