基于MPI模擬退火算法求解貨郎擔(dān)問(wèn)題的并行算法.doc

《基于MPI模擬退火算法求解貨郎擔(dān)問(wèn)題的并行算法.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、基于MPI的模擬退火算法求解貨郎擔(dān)問(wèn)題的并行算法#include"mpi.h"#include#include#include#include#definemaxn51#definemaxnp100#definemaxlp5000intmyrandom(intm){returnabs(((clock()*rand()))%m);}floatmyrandom0_1(){return((float)myrandom(32767)/32767.f);}floa

2、tdist(intx1,inty1,intx2,inty2){returnsqrt((float)(x1-x2)*(float)(x1-x2)+(float)(y1-y2)*(float)(y1-y2));}voidinit_d(intx[maxn],inty[maxn],floatd[maxn][maxn],intpath[maxn],intn){inti,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]);}8

3、for(i=1;i<=n;i++)for(j=i;j<=n;j++)d[i][j]=d[j][i];}voidgenerate(intn,int*r,int*m,intc[7]){inti;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(i<3);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;i

4、f(*r==3){c[5]=1+(c[2]+myrandom(abs(i-2)))%n;c[6]=1+c[5]%n;*m=6;}}floatdelta_length(intr,intm,intc0[7],intp[maxn],floatd[maxn][maxn]){floatdf;intj,c[7];for(j=1;j<=m;j++)8c[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]];elsedf=d[c[1]]

5、[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);}intaccept(floatt,floatdf){return(df<0.0)

6、

7、((df/t<88.)&&(exp(-df/t)>myrandom0_1()));}voidtwochain(intn,intc[7],intp[maxn]){inti,j,u,v,w;i=(1+(c[2]-c[1]+n)%n)/2;for(j=1;j<=i;j++

8、){u=1+(c[1]+j-2)%n;v=1+(c[2]-j+n)%n;w=p[u];p[u]=p[v];p[v]=w;}}voidthreechain(intn,intc[7],intp[maxn]){intp0[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;8i=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

9、++){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];}floatannealing(intn,intlp,ints,floatt,floatdt,intp[maxn],floatd[maxn][maxn]){floatdf,f=0;intc[7],k,r,m,a,s0=0;for(k=1;k

10、f=f+d[p[n]][p[1]];do{a=0;for(k=1;k<=lp;k++)8{generate(n,&r,&m,c);df=delta_length(r,m,c,p,d);if(accept(t,df)==1){if(r==2)twochain(n,c,p);elsethreechain(n