基于MPI的模拟退火算法求解货郎担问题的并行算法算法.doc

PAGE 1 基于MPI的模拟退火算法求解货郎担问题的并行算法 #include mpi.h #include math.h #include stdio.h #include stdlib.h #include time.h #define maxn 51 #define maxnp 100 #define maxlp 5000 int myrandom(int m) { return abs(((clock()*rand()))%m); } float myrandom0_1() { return((float)myrandom(32767)/32767.f); } float dist(int x1,int y1,int x2,int y2) { return sqrt((float)(x1-x2)*(float)(x1-x2)+(float)(y1-y2)*(float)(y1-y2)); } void init_d(int x[maxn],int y[maxn],float d[maxn][maxn],int path[maxn],int n) { int i,j; for(i=1;i=n;i++) { path[i]=i; for(j=1;j=i;j++) d[i][j]=dist(x[i],y[i],x[j],y[j]); } for(i=1;i=n;i++) for(j=i;j=n;j++) d[i][j]=d[j][i]; } void generate(int n,int *r,int *m,int c[7]) { int i; do { c[1]=1+myrandom(n); c[2]=1+myrandom(n-1); if(c[2]==c[1]) c[2]++; i=1+(c[1]-c[2]+n-1)%n; }while(i3); c[3]=1+(c[1]+n-2)%n; c[4]=1+c[2]%n; c[5]=0; c[6]=0; *r=2+myrandom(2); *m=4; if(*r==3) { c[5]=1+(c[2]+myrandom(abs(i-2)))%n; c[6]=1+c[5]%n; *m=6; } } float delta_length(int r,int m,int c0[7],int p[maxn],float d[maxn][maxn]) { float df; int j,c[7]; for(j=1;j=m;j++) c[j]=p[c0[j]]; if(r==2) df=d[c[1]][c[4]]+d[c[2]][c[3]]-d[c[1]][c[3]]-d[c[2]][c[4]]; else df=d[c[1]][c[5]]+d[c[2]][c[6]]+d[c[3]][c[4]]-d[c[1]][c[3]]-d[c[2]][c[4]]-d[c[5]][c[6]]; return(df); } int accept(float t,float df) { return (df0.0)||((df/t88.)(exp(-df/t)myrandom0_1())); } void twochain(int n,int c[7],int p[maxn]) { int i,j,u,v,w; i=(1+(c[2]-c[1]+n)%n)/2; for(j=1;j=i;j++) { u=1+(c[1]+j-2)%n; v=1+(c[2]-j+n)%n; w=p[u]; p[u]=p[v]; p[v]=w; } } void threechain(int n,int c[7],int p[maxn]) { int p0[maxn],i,j,m1,m2,m3,w; m1=1+(c[2]-c[1]+n)%n; m2=1+(c[3]-c[6]+n)%n; m3=1+(c[5]-c[4]+n)%n; i=1; for(j=1;j=m1;j++) { w=1+(j+c[1]-2)%n; p0[i]=p[w]; i++; } for(j=1;j=m2;j++) { w=1+(j+c[6]-2)%n; p0[i]=p[w]; i++; } for(j=1;j=m3;j++) { w=1+(j+c[4]-2)%n; p0[i]=p[w]; i++; } for(j=1;j=n;j++) p[j]=p0[j]; } float annealing(int n, int lp, int s