#include <stdio.h>#include <mpi.h>/*定義距離的最大值*/#define MAXDISTANCE 999999/*定義點(diǎn)的最大個(gè)數(shù)*/#define MAXPOINT    20int my_rank,group_size,n;int point[MAXPOINT];double dist[MAXPOINT][MAXPOINT];double maxvalue[MAXPOINT];int flag=1;void sub_tsp(int rank){    int itemp,jtemp,ijtemp,k;    double temp;    int i,j;    for(i=0;i<n-2;i++)        for(j=i+2;j<n;j++)    {		/*分配給相應(yīng)的處理器*/        if(my_rank==((i+j)%group_size))        {			/*求出對(duì)邊（i ，j）的改進(jìn)權(quán)*/            temp=dist[point[i]][point[i+1]]+dist[point[j]][point[j+1]]-dist[point[i]][point[j]]-dist[point[i+1]][point[j+1]];			/*判斷是不是更大的改進(jìn)權(quán)*/            if(temp>maxvalue[rank])            {                maxvalue[rank]=temp;                itemp=i;                jtemp=j;            }        }    }	/*如果最大的改進(jìn)權(quán)大于0，相應(yīng)的對(duì)邊(itemp，jtemp)，則進(jìn)行位置的調(diào)整，改良原來的Hamilton圈*/    if(maxvalue[rank]>0)    {        for(k=itemp+1;k<=(itemp+1+jtemp)/2;k++)        {            ijtemp=point[k];            point[k]=point[itemp+jtemp+1-k];            point[itemp+jtemp+1-k]=ijtemp;        }    }    return;}/*求最大改進(jìn)權(quán)*/int selectmax(){    int i,j;    double temp=0;    for(i=0;i<group_size;i++)    {        if(maxvalue[i]>temp)        {            j=i;            temp=maxvalue[i];        }    }    if(temp==0)        return -1;    return j;}/*輸出較優(yōu)的回路和回路的總長(zhǎng)度*/void output(){    int i;    double sum=0.0;    for(i=0;i<n;i++)        sum+=dist[point[i]][point[i+1]];	/*如果算法運(yùn)行結(jié)束的時(shí)候，得到的Hamilton圈的長(zhǎng)度大于距離的最大值，說明原圖中不存在圈*/    if((sum>=MAXDISTANCE)&&(flag==0))    {        printf("原圖中不存在圈!  \n");        return;    }    for(i=0;i<n;i++)        printf("%d->",point[i]);    printf("%d\n",point[n]);    printf("距離的和是%.1lf\n",sum);    return;}void main(int argc,char *argv[]){    int i,j;    MPI_Status status;	/*啟動(dòng)計(jì)算*/    MPI_Init(&argc,&argv);	/*找自己的id，存放在my_rank 中*/    MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);	/*找進(jìn)程數(shù)，存放在group_size 中*/    MPI_Comm_size(MPI_COMM_WORLD,&group_size);	/*輸入點(diǎn)之間的距離矩陣*/    if(my_rank==0)    {		/*輸入點(diǎn)的個(gè)數(shù)，存放在n中*/        printf("請(qǐng)輸入點(diǎn)的個(gè)數(shù):");        scanf("%d",&n);		/*點(diǎn)的個(gè)數(shù)不能大于MAXPOINT*/        if(n>MAXPOINT)        {            printf("點(diǎn)的個(gè)數(shù)不能大于%d!  \n",MAXPOINT);            goto terminal;        }		/*排除n＝0，1，2的情況*/        if(n<3)        {            printf("TSP 問題在n＝%d的情況下沒意義！！  \n",n);            goto terminal;        }		/* 輸入點(diǎn) i和點(diǎn)j之間的 距離，存放在dist[i][j]*/        for(i=0;i<n-1;i++)        {            for(j=i+1;j<n;j++)            {                printf("%d<->%d: ",i,j);                scanf("%lf",&dist[i][j]);                dist[j][i]=dist[i][j];            }        }        for(i=0;i<=n;i++)        {            dist[i][i]=0;            dist[n][i]=dist[0][i];            dist[i][n]=dist[i][0];        }    }	/*從根進(jìn)程向所有進(jìn)程發(fā)送n*/    MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD);	/*同步所有進(jìn)程*/    MPI_Barrier(MPI_COMM_WORLD);	/*從根進(jìn)程向所有進(jìn)程發(fā)送點(diǎn)0到其他點(diǎn)的距離*/    for(i=0;i<=n;i++)        MPI_Bcast(&dist[i][0],n+1,MPI_DOUBLE,0,MPI_COMM_WORLD);    MPI_Barrier(MPI_COMM_WORLD);	/*構(gòu)造初始的Hamilton圈0－>1－>2－> ...... －>n-1－>0*/    for(i=0;i<=n;i++)        point[i]=i%n;	/*flag標(biāo)志還能不能對(duì)Hamilton圈進(jìn)行改良*/    while(flag==1)    {		/*輸出每次改良后的Hamilton圈及其總長(zhǎng)度*/        if(my_rank==0)            output();        maxvalue[my_rank]=0;        sub_tsp(my_rank);		/*非根進(jìn)程將所有的改進(jìn)權(quán)傳遞到0處理器*/        if(my_rank>0)            MPI_Send(&maxvalue[my_rank],1,MPI_DOUBLE,0,my_rank,MPI_COMM_WORLD);		/*根進(jìn)程接受其他進(jìn)程的改進(jìn)權(quán)，由其判斷最大的改進(jìn)權(quán)*/        if(my_rank==0)        {            for(i=1;i<group_size;i++)                MPI_Recv(&maxvalue[i],1,MPI_DOUBLE,i,i,MPI_COMM_WORLD,&status);            j=selectmax();        }        MPI_Barrier(MPI_COMM_WORLD);		/*從根進(jìn)程向所有進(jìn)程發(fā)送點(diǎn)最大的改進(jìn)權(quán)*/        MPI_Bcast(&j,1,MPI_INT,0,MPI_COMM_WORLD);        MPI_Barrier(MPI_COMM_WORLD);		/*如果最大改進(jìn)權(quán)為0，則表示沒有任何改進(jìn)，不能再對(duì)Hamilton圈進(jìn)行改良*/        if(j==-1)            flag=0;		/*否則將最大權(quán)對(duì)應(yīng)的處理器rank值廣播到處理器中，對(duì)應(yīng)的處理器得到改進(jìn)的圈*/        else            MPI_Bcast(point,n+1,MPI_INT,j,MPI_COMM_WORLD);    }	/*輸出計(jì)算的最終結(jié)果*/    if(my_rank==0)        output();	/*結(jié)束計(jì)算*/    terminal:    MPI_Finalize();}