贪婪法解货郎担问题

《贪婪法解货郎担问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、/*按以下贪婪法求解货郎担问题。货郎担问题是指给定一个无向图，已知各顶点的坐标,能求出各顶点之间边的权。要在在这个图中找一个闭合回路，使回路经过图中的每一个点,而回路各边的权之和为最小。求解货郎担问题的贪婪算法如下：{1、输入无向图的顶点数n(设各点依次自0开始顺序连续编号)；2、顺序输入各顶点的坐标；3、计算边的权,及累计边数(n*(n-l)/2)；4、建立按边的权自小到大排序的边权顺序表；5、用贪婪算法，选择边。入选的边必须符合以下两个条件：5.1不会使该边的每个顶点与两条以上已入选边相联系

2、。5.2不会因入选的边形成回路，除非该边入选后，正好边数等于顶点数。}为存储入选边的信息，可用顶点联系表，该表的表元有三个成分：与该顶点相连的已入选的边数，与该顶点相连的顶点1,与该点相连的顶点2。与每个顶点相连的边只能有两条入选，故最多只有两个别的顶点与它相连。如果由(5)找不到解，可适当调整边权顺序表，改变相同边权的次序。重新执行(5)o如果找到解，就能从端点联系表求出回路的轨迹。选择边(i,j)合理，首先是这条边的加入，使这两个顶点只与一个顶点相连；该边加入会使其中一个顶点与3个顶点相连，

3、则这条边的加入是不合理的。另外，这条边的加入,使与早先加入的边构成回路，则是不合理的；否则，是合理的。为了能判定边(i,j)的入选是否会构成回路，有两种办法：1)临时复制出一个顶点联系表，并将边(i,j)入选，然后反复去掉其中已只与一个顶点相连的顶点，最后若还有与两个顶点相连的顶点，并且这样的顶点数大于等于3个，则说明边(i,j)的入选将会构成回路。2)由于路线中一个顶点最多只能与两个顶点相连，可从i顶点出发，沿着选中的连，往前走，如能走到j顶点，贝0加入边(i,j)将构成回路；如在走的过程中到

4、了还只有与一个顶点相连的顶点，则不会构成回路。【程序】*/^includettincludettdefineMAXN300^definePN30^defineSQR2(x,y)(x)*(x)+(y)*(y)typedefstruct{intp⑵;doubled;}TDR;/*两顶点及之间的距离*/typedefstruct{intn;intp[2];}TR;//相联顶点数，相联的顶点typedefstruct{doublex,y;}POINT;/*点的类型，X坐

5、标、Y坐标*/TDRdr[MAXN];/*边长表*/TRr[PN];/*顶点联系表*/POINTp[PN];intpn;intdistance(POINT*pp,intn,TDR*t)//求所有顶点对之间的矩离{intk,i,j;for(k=i=0;i

6、d(TDR*t,intn)//排序{TDRtemp;intk,m,j;m=n-1;while(m>0){for(k=j=0;jt[j+l].d){temp=t[j];t[j]=t[j+l];t[j+l]=temp;k=j;}m=k;}}voidselect(TR*r,inti,intj){r[i]・p[r[i]・n++]=j;//i接上j,i的度增1,顶点j成为i的联系顶点r[j].p[r[j].n++]=i;//j接上i,j的度增1,顶点i成为j的联系顶点}intiscirc

7、uit(TR*r,intn,inti,intj){intk,u;TRtr[PN]:if(r[i].n==2

8、

9、r[j].n==2)return1;if(r[i]・n二二0

10、

11、r[j]・n==0)return0;/*自i顶点岀发，顺着已选中的边能走到j,则表示加入边(i,j)将产生回路intk0=i,kl=r[i].p[0];intloop=0;while(kl!=j){kt=kO;kO=kl;if(r[kl].n==1)return0;kl=r[kl].p[0]=kt?r[kl].p[l]:r[

12、kl].p[0];}return1;*/for(u=0;u