tsp.c
上传用户:hhyinxing
上传日期:2013-09-10
资源大小:833k
文件大小:4k
源码类别:

并行计算

开发平台:

Unix_Linux

  1. #include <stdio.h>
  2. #include <mpi.h>
  3. /*定义距离的最大值*/
  4. #define MAXDISTANCE 999999
  5. /*定义点的最大个数*/
  6. #define MAXPOINT    20
  7. int my_rank,group_size,n;
  8. int point[MAXPOINT];
  9. double dist[MAXPOINT][MAXPOINT];
  10. double maxvalue[MAXPOINT];
  11. int flag=1;
  12. void sub_tsp(int rank)
  13. {
  14.     int itemp,jtemp,ijtemp,k;
  15.     double temp;
  16.     int i,j;
  17.     for(i=0;i<n-2;i++)
  18.         for(j=i+2;j<n;j++)
  19.     {
  20. /*分配给相应的处理器*/
  21.         if(my_rank==((i+j)%group_size))
  22.         {
  23. /*求出对边(i ,j)的改进权*/
  24.             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]];
  25. /*判断是不是更大的改进权*/
  26.             if(temp>maxvalue[rank])
  27.             {
  28.                 maxvalue[rank]=temp;
  29.                 itemp=i;
  30.                 jtemp=j;
  31.             }
  32.         }
  33.     }
  34. /*如果最大的改进权大于0,相应的对边(itemp,jtemp),则进行位置的调整,改良原来的Hamilton圈*/
  35.     if(maxvalue[rank]>0)
  36.     {
  37.         for(k=itemp+1;k<=(itemp+1+jtemp)/2;k++)
  38.         {
  39.             ijtemp=point[k];
  40.             point[k]=point[itemp+jtemp+1-k];
  41.             point[itemp+jtemp+1-k]=ijtemp;
  42.         }
  43.     }
  44.     return;
  45. }
  46. /*求最大改进权*/
  47. int selectmax()
  48. {
  49.     int i,j;
  50.     double temp=0;
  51.     for(i=0;i<group_size;i++)
  52.     {
  53.         if(maxvalue[i]>temp)
  54.         {
  55.             j=i;
  56.             temp=maxvalue[i];
  57.         }
  58.     }
  59.     if(temp==0)
  60.         return -1;
  61.     return j;
  62. }
  63. /*输出较优的回路和回路的总长度*/
  64. void output()
  65. {
  66.     int i;
  67.     double sum=0.0;
  68.     for(i=0;i<n;i++)
  69.         sum+=dist[point[i]][point[i+1]];
  70. /*如果算法运行结束的时候,得到的Hamilton圈的长度大于距离的最大值,说明原图中不存在圈*/
  71.     if((sum>=MAXDISTANCE)&&(flag==0))
  72.     {
  73.         printf("原图中不存在圈!  n");
  74.         return;
  75.     }
  76.     for(i=0;i<n;i++)
  77.         printf("%d->",point[i]);
  78.     printf("%dn",point[n]);
  79.     printf("距离的和是%.1lfn",sum);
  80.     return;
  81. }
  82. void main(int argc,char *argv[])
  83. {
  84.     int i,j;
  85.     MPI_Status status;
  86. /*启动计算*/
  87.     MPI_Init(&argc,&argv);
  88. /*找自己的id,存放在my_rank 中*/
  89.     MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);
  90. /*找进程数,存放在group_size 中*/
  91.     MPI_Comm_size(MPI_COMM_WORLD,&group_size);
  92. /*输入点之间的距离矩阵*/
  93.     if(my_rank==0)
  94.     {
  95. /*输入点的个数,存放在n中*/
  96.         printf("请输入点的个数:");
  97.         scanf("%d",&n);
  98. /*点的个数不能大于MAXPOINT*/
  99.         if(n>MAXPOINT)
  100.         {
  101.             printf("点的个数不能大于%d!  n",MAXPOINT);
  102.             goto terminal;
  103.         }
  104. /*排除n=0,1,2的情况*/
  105.         if(n<3)
  106.         {
  107.             printf("TSP 问题在n=%d的情况下没意义!!  n",n);
  108.             goto terminal;
  109.         }
  110. /* 输入点 i和点j之间的 距离,存放在dist[i][j]*/
  111.         for(i=0;i<n-1;i++)
  112.         {
  113.             for(j=i+1;j<n;j++)
  114.             {
  115.                 printf("%d<->%d: ",i,j);
  116.                 scanf("%lf",&dist[i][j]);
  117.                 dist[j][i]=dist[i][j];
  118.             }
  119.         }
  120.         for(i=0;i<=n;i++)
  121.         {
  122.             dist[i][i]=0;
  123.             dist[n][i]=dist[0][i];
  124.             dist[i][n]=dist[i][0];
  125.         }
  126.     }
  127. /*从根进程向所有进程发送n*/
  128.     MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD);
  129. /*同步所有进程*/
  130.     MPI_Barrier(MPI_COMM_WORLD);
  131. /*从根进程向所有进程发送点0到其他点的距离*/
  132.     for(i=0;i<=n;i++)
  133.         MPI_Bcast(&dist[i][0],n+1,MPI_DOUBLE,0,MPI_COMM_WORLD);
  134.     MPI_Barrier(MPI_COMM_WORLD);
  135. /*构造初始的Hamilton圈0->1->2-> ...... ->n-1->0*/
  136.     for(i=0;i<=n;i++)
  137.         point[i]=i%n;
  138. /*flag标志还能不能对Hamilton圈进行改良*/
  139.     while(flag==1)
  140.     {
  141. /*输出每次改良后的Hamilton圈及其总长度*/
  142.         if(my_rank==0)
  143.             output();
  144.         maxvalue[my_rank]=0;
  145.         sub_tsp(my_rank);
  146. /*非根进程将所有的改进权传递到0处理器*/
  147.         if(my_rank>0)
  148.             MPI_Send(&maxvalue[my_rank],1,MPI_DOUBLE,0,my_rank,MPI_COMM_WORLD);
  149. /*根进程接受其他进程的改进权,由其判断最大的改进权*/
  150.         if(my_rank==0)
  151.         {
  152.             for(i=1;i<group_size;i++)
  153.                 MPI_Recv(&maxvalue[i],1,MPI_DOUBLE,i,i,MPI_COMM_WORLD,&status);
  154.             j=selectmax();
  155.         }
  156.         MPI_Barrier(MPI_COMM_WORLD);
  157. /*从根进程向所有进程发送点最大的改进权*/
  158.         MPI_Bcast(&j,1,MPI_INT,0,MPI_COMM_WORLD);
  159.         MPI_Barrier(MPI_COMM_WORLD);
  160. /*如果最大改进权为0,则表示没有任何改进,不能再对Hamilton圈进行改良*/
  161.         if(j==-1)
  162.             flag=0;
  163. /*否则将最大权对应的处理器rank值广播到处理器中,对应的处理器得到改进的圈*/
  164.         else
  165.             MPI_Bcast(point,n+1,MPI_INT,j,MPI_COMM_WORLD);
  166.     }
  167. /*输出计算的最终结果*/
  168.     if(my_rank==0)
  169.         output();
  170. /*结束计算*/
  171.     terminal:
  172.     MPI_Finalize();
  173. }