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

《基于MPI模拟退火算法求解货郎担问题并行算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于MPI的模拟退火算法求解货郎担问题的并行算法#include"mpi.h"#include#include#include#include#definemaxn51#definemaxnp100#definemaxlp5000intmyrandom(intm){returnabs(((clock()*rand()))%m);}floatmyrandom0_1(){return((float)myrandom(32767)/32767.f);}floatdist(intx1,inty1,in

2、tx2,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]);}8for(i=1;i<=n;i++)for(j=i;j<=n;j++)d[i][j

3、]=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;if(*r==3){c[5]=1+(c[2]+myrandom(abs(i-2)))%n;c[6]=1+c[5]%n;*m

4、=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]][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]];ret

5、urn(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++){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]

8、){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++){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];}fl

9、oatannealing(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、threechain(n