第四讲贪心算法

《第四讲贪心算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四讲贪心算法组网问题打算把一组计算机通过连接所选的计算机对组建成一个网络。每条链与一个维护成本相联系。图的形成:节点计算机边链边权维护成本最便宜的网络是什么？解决方案：(i)必须连接所有节点(ii)不能包含圈，因为这种情况下可能有更便宜的网络。断言删除一个圈不会断开一个图。因此答案是树（连通且无圈）树一个连通且无圈的无向图称作树一棵树有多少边?一棵有n个节点的树有n-1条边树的性质-1断言：一棵有n个节点的数有n-1条边为了理解这点，一个时刻建树的一条边...开始时刻：n节点,无边n连通分量当添加一条边e时：(i)e的

2、端点必须在不同的分量中(否则产生一个圈)(ii)添加e合并二个连通分量(iii)连通分量数减1在结束时刻：一个连通分量因此：按照这种方法，n-1肯定被添加。树的性质-2每个有

3、V

4、-1条边的图是树吗？断言：任何连通无向图，如果

5、E

6、=

7、V

8、-1则必然是树。证明：假设G是连通且无向的图，

9、E

10、=

11、V

12、-1.在G上运行下列过程：whileithasacycle:removeacycleedge结果:G’=(V,E’)whereE’⊆E。G’连通且无圈:因此是棵树。由于G’是棵树,因此

13、E’

14、=

15、V

16、-1.这样E’=E,因此没

17、有边被移去，从而G开始就是棵树。可以通过数一棵连通图有多少条边来判断图是否是树。组网打算把一组计算机通过连接所选的计算机对组建成一个网络。每条链与一个维护成本相联系。最便宜的网络是什么？最小生成树(MST)输入:图G=(V,E);边的权we输出:树T=(V,E’),E’E目标:最小化最小生成树的数量是指数级:因此不能采用每棵树都去试的方法。而是采用贪心算法:一个时刻添一条树边...假设已经选取了一些边XE,目前是OK(即.X是某个MST的一部分).下一步添加哪条边?割的性质断言:设X⊂E是图G=(V,E)的某个最小生成树

18、T的一部分。选取一个节点子集S⊂V使得X在S和V-S之间无边。设e是S和V-S之间最轻的边。那么X∪{e}是某个MSTT’的一部分,证明：如果e在T中,结论自然成立。因此假设不在。添加e到T;这产生唯一的圈C。这个圈有另外一条边跨S和V-S;称它为e’.T’=T+e–e’是连通的。它有

19、V

20、-1条边，因此，它是棵树。cost(T’)=cost(T)+w(e)–w(e’)≤cost(T)因此T’也是一棵MST,且包含X∪{e}.一般MST算法X={}//edgespickedsofarrepeatuntil

21、X

22、=

23、V

24、-

25、1:pickasetSVsuchthatXhasnoedgesbetweenSandV-SletebethelightestedgebetweenSandV-SX=X∪{e}Kruskal算法X={}foralledgeseinorderofincreasingweight:ifaddingetoXdoesnotcreateacycle:X=X∪{e}为什么这是正确的？Kruskal算法procedurekruskal(G,w)input:graphG=(V,E);edgeweightsweoutput:Xcontai

26、nstheedgesofanMSTX={}forallnodesu:makeset(u)foredges(u,v)inorderofincreasingweight:iffind(u)≠find(v):X=X∪{(u,v)}union(u,v)X={}foralleinorderofincreasingwe:ifedoesnotcreateacycleinX:addetoX起初每个节点自身是个连通分量。当添加一条边(u,v)时,u,v的连通分量合并需要一种数据结构来维护不相交集合。操作:makeset(x)形成一个仅仅含

27、x的集合。find(x)x属于哪个集合？union(x,y)合并包含x和y的集合。时间:O(ElogE)+(V-1)xunion+2ExfindUnion-find数据结构proceduremakeset(x)p[x]=xrank[x]=0procedurefind(x)whilex≠p[x]:x=p[x]returnx操作:makeset(x)形成一个仅仅含x的集合。find(x)X属于哪个集合？union(x,y)合并包含x和y的集合。每个集合存储为一个有向树。如，二个集合{b,e}和{a,c,d,f,g,h}：父母

28、指针:p(b)=e,p(g)=d,等.每个集合的根是它的代表（或名称）。每个节点有个数值rank.Union很容易：只须将根指针指向另一树的根！通过rank合并对并操作的二种选择：选择1:root=e选择2:root=h每个节点有个数值rank.根节点的rank和树的高度相关。让rank较小的根指向rank较大的根。