阅读下列函数说明和C代码, [说明] 所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。 应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(

admin2013-01-05  29

问题 阅读下列函数说明和C代码,
   [说明]
   所谓货郎担问题,是指给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和最小。
   应用贪婪法求解该问题,程序先计算由各点构成的所有边的长度(作为边的权值),按长度大小对各边进行排序后,按贪婪准则从排序后的各边中选择组成回路的边,贪婪准则使得边的选择按各边长度从小到大选择。
   函数中使用的预定义符号如下:
   #define M 100
   typedef struct{/*x为两端点p1、p2之间的距离,p1、p2所组成边的长度*/
   float x;
   int p1,p2;
   }tdr;
   typedef struct{/*p1、p2为和端点相联系的两个端点,n为端点的度*/
   int n,p1,p2;
   }tr;
   typedef struct{/*给出两点坐标*/
   float x,y;
   }tpd;
   typedef int tl[M];
   int n=10;
   [函数]
   float distance(tpd a,tpd b);/*计算端点a、b之间的距离*/
   void sortArr(tdr a[M],int m);
   /*将已经计算好的距离关系表按距离大小从小到大排序形成排序表,m为边的条数*/
   int isCircuit(tr r[M],int i,int j);
   /*判断边(i,j)选入端点关系表r[M]后,是否形成回路,若形成回路返回0*/
   void selected(tr r[M],int i,int j);/*边(i,j)选入端点关系表r*/
   void course(tr r [M],tl l[M]);/*从端点关系表r中得出回路轨迹表*/
   void exchange(tdr a[M],int m,int b);
   /*调整表排序表,b表示是否可调,即是否有长度相同的边存在*/
   void travling(tpd pd [M],int n,float dist,tl locus[M])
   /*dist记录总路程*/
   {
   tdr dr[M];/*距离关系表*/
   tr r[M];/*端点关系表*/
   int i,j,k,h,m;/*h表示选入端点关系表中的边数*/
   int b;/*标识是否有长度相等的边*/
   k=0;
   /*计算距离关系表中各边的长度*/
   for(i=1;i<n; i++){
   for(j=i+1;J<=n;j++){
   k++;
   dr[k].x=(1);
   dr[k].pl=i;
   dr[k].p2=j;
   }
   }
   m=k;
   sortArr(dr,m);/*按距离大小从小到大排序形成排序表*/
   do{
   b=1;
   dist=0;
   k=h=0:
   do{
   k++;
   i=dr[k].p1;
   j=dr[k].p2;
   if((r(i].n<=1)&&(r[j].n<=1)){/*度数不能大于2*/
   if  (2)  {
   /*若边(i,j)加入r后形成回路,则不能加入*/
     (3);
   h++;
   dist+=dr[k].x;
   }else if  (4)  {
   /*最后一边选入r成回路,则该边必须加入且得到解*/
   selected(r,i,j);
   h++:
   dist+=dr[k].x;
   }
   }
   }while((k !=n)  &&  (h !=n));
   if(h==n){/*最后一边选入构成回路,完成输出结果*/
   course(r,locus);
   }else(/*找不到解,调整dr,交换表中边长相同的边在表中的顺序,并将b置0*/
     (5);
   }
   }while(!b);
   }
(2)

选项

答案!isCircuit(r,i,j)

解析 由注释可见空(2)是判断边(i,j)加入r后是否形成回路,若形成了回路,不加入,由语句“dist+=dr[k].x;”可知此处是将边加入,故此处应该是不形成回路条件。参照isCircuit函数声明及说明可知,若形成回路返回0,故空(2)填!isCircuit(r,j)。
转载请注明原文地址:https://kaotiyun.com/show/MYDZ777K
0

相关试题推荐
最新回复(0)