中国数学建模-编程交流-贪婪算法_2

《中国数学建模-编程交流-贪婪算法_2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中国数学建模-编程交流-贪婪算法_2├编程交流├学术杂谈├EnglishFanswh-ee重登录隐身用户控制面板搜索风格论坛状态论坛展区社区服务社区休闲网站首页退出>>VC++,C,Perl,Asp...编程学习,算法介绍.我的收件箱(0)中国数学建模→学术区→编程交流→贪婪算法您是本帖的第890个阅读者*贴子主题：贪婪算法b等级：职业侠客文章：470积分：956门派：黑客帝国注册：2003-8-28第11楼1.3.6最小耗费生成树在例1-2及1-3中已考察过这个问题。因为具有n个顶点的无向网络G的每个生成树刚好具有n-1条边，所以问题是用某种方法选择n-1条边使它们形成G的最小生成

2、树。至少可以采用三种不同的贪婪策略来选择这n-1条边。这三种求解最小生成树的贪婪算法策略是：Kruskal算法，Prim算法和Sollin算法。1.Kruskal算法(1)算法思想Kruskal算法每次选择n-1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。Kruskal算法分e步，其中e是网络中边的数目。按耗费递增的顺序来考虑这e条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。考察图1-12a中的网络。初始时没有任何边被选择。图

3、13-12b显示了各节点的当前状态。边（1,6）是最先选入的边，它被加入到欲构建的生成树中，得到图13-12c。下一步选择边（3，4）并将其加入树中（如图13-12d所示）。然后考虑边(2，7)，将它加入树中并不会产生环路，于是便得到图13-12e。下一步考虑边（2，3）并将其加入树中（如图13-12f所示）。在其余还未考虑的边中，（7，4）具有最小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。此后将边（5，4）加入树中，得到的树如图13-12g所示。下一步考虑边（7，5），由于会产生环路，将其丢弃。最后考虑边（6，5）并将其加入树中，产生了一棵生成树，其耗费为99

4、。图1-13给出了Kruskal算法的伪代码。//在一个具有n个顶点的网络中找到一棵最小生成树令T为所选边的集合，初始化T=令E为网络中边的集合while(E≠)&&(

5、T

6、≠n-1){令(u,v)为E中代价最小的边E=E-{(u,v)}//从E中删除边if((u,v)加入T中不会产生环路)将（u,v）加入T}if(

7、T

8、==n-1)T是最小耗费生成树else网络不是互连的，不能找到生成树图13-13Kruskao算法的伪代码(2)正确性证明利用前述装载问题所用的转化技术可以证明图13-13的贪婪算法总能建立一棵最小耗费生成树。需要证明以下两点：1)只要存在生成树，Kruskal算法总能

9、产生一棵生成树；2)产生的生成树具有最小耗费。令G为任意加权无向图（即G是一个无向网络）。从12.11.3节可知当且仅当一个无向图连通时它有生成树。而且在Kruskal算法中被拒绝（丢弃）的边是那些会产生环路的边。删除连通图环路中的一条边所形成的图仍是连通图，因此如果G在开始时是连通的，则T与E中的边总能形成一个连通图。也就是若G开始时是连通的，算法不会终止于E=和

10、T

11、

12、≠U，令k(k>0)为在T中而不在U中的边的个数，当然k也是在U中而不在T中的边的数目。通过把U变换为T来证明U与T具有相同的耗费，这种转化可在k步内完成。每一步使在T而不在U中的边的数目刚好减1。而且U的耗费不会因为转化而改变。经过k步的转化得到的U将与原来的U具有相同的耗费，且转化后U中的边就是T中的边。由此可知，T具有最小耗费。每步转化包括从T中移一条边e到U中，并从U中移出一条边f。边e与f的选取按如下方式进行：1)令e是在T中而不在U中的具有最小耗费的边。由于k>0，这条边肯定存在。2)当把e加入U时，则会形成唯一的一条环路。令f为这条环路上不在T中的任意一条边。由于T中不含环

13、路，因此所形成的环路中至少有一条边不在T中。从e与f的选择方法中可以看出，V=U+{e}-{f}是一棵生成树，且T中恰有k-1条边不在V中出现。现在来证明V的耗费与U的相同。显然，V的耗费等于U的耗费加上边e的耗费再减去边f的耗费。若e的耗费比f的小，则生成树V的耗费比U的耗费小，这是不可能的。如果e的耗费高于f，在Kruskal算法中f会在e之前被考虑。由于f不在T中，Kruskal算法在考虑f能否加入T时已将f丢弃，因此f和T中