《通信网络理论基础第6讲树与流-XXXX-BIG课件精编版》由会员分享，可在线阅读，更多相关《通信网络理论基础第6讲树与流-XXXX-BIG课件精编版（51页珍藏版）》请在金锄头文库上搜索。
1、通信网络理论基础,Part 06: 树与流,2014年春季 通信网络理论基础,2 / 50,树与流,1,最小生成树算法,最小生成树的各种解法突出地显示了贪婪算法的力量。,3 / 50,最小生成树算法,请着重体会：最优条件与算法的关系.,采用类似思路,综合了两个算法的思路,2014年春季 通信网络理论基础,4 / 50,最小生成树算法,4,最优性条件,1,2,3,5,Kruskal算法,Prim算法,Sollin算法,Steiner树问题,2014年春季 通信网络理论基础,路径最优条件,5 / 50,2014年春季 通信网络理论基础,树上边与割集,6 / 50,S2,S1,2014年春季 通信网
2、络理论基础,割最优条件,7 / 50,S2,S1,2014年春季 通信网络理论基础,8 / 50,最小生成树算法,4,最优性条件,1,2,3,5,Kruskal算法,Prim算法,Sollin算法,Steiner树问题,2014年春季 通信网络理论基础,从最优条件到算法,9 / 50,2014年春季 通信网络理论基础,10 / 50,Kruskal算法思想,把原图中所有边按权重的升序排序；,一开始把原图看作一个森林，含n棵树；,按序、逐条地检查边：,直至只剩下一棵树（或者留下来的边的数目为n1）。,剩下没检查的边都必然是非树上边，且权重更大。,2014年春季 通信网络理论基础,路径最优条件在哪
3、里？,11 / 50,结论：由于路径最优条件，所以Kruskal算法是正确的。,2014年春季 通信网络理论基础,一个例子,12 / 50,10,15,20,35,2014年春季 通信网络理论基础,Kruskal算法实现,13 / 50,请再次体会数据结构的力量：采用下述数据结构设计后，复杂度从O(nm)降为O(m+nlogn)。,看两个顶点的first是否相同。,比较size；将较小的树插入到 较大的树后面（last）。,因为排在后面的list中的顶点 都要更新其first值。,2014年春季 通信网络理论基础,14 / 50,最小生成树算法,4,最优性条件,1,2,3,5,Kruskal算
4、法,Prim算法,Sollin算法,Steiner树问题,2014年春季 通信网络理论基础,Prim算法,15 / 50,Kruskal算法,Prim算法,2014年春季 通信网络理论基础,Prim算法伪码,16 / 50,DijkstraAlg (G(V, E), s),PrimAlg (G(V, E), s),2014年春季 通信网络理论基础,17 / 50,最小生成树算法,4,最优性条件,1,2,3,5,Kruskal算法,Prim算法,Sollin算法,Steiner树问题,2014年春季 通信网络理论基础,Sollin算法,18 / 50,Sollin算法可以看作是Kruskal和P
5、rim两个算法的综合。,从森林开始，通过合并树最终求得生成树；,合并时，总是挑选最小权重的割边。,Kruskal算法,Prim算法,2014年春季 通信网络理论基础,Sollin算法伪码,19 / 50,2014年春季 通信网络理论基础,一个例子,20 / 50,2014年春季 通信网络理论基础,21 / 50,最小生成树算法,4,最优性条件,1,2,3,5,Kruskal算法,Prim算法,Sollin算法,Steiner树问题,2014年春季 通信网络理论基础,Steiner树问题,22 / 50,2014年春季 通信网络理论基础,SPH算法,23 / 50,求X中各个顶点对之间的最短路，
6、其中最短的作为初始树T；,求X中其他顶点到T的最短路，把其中最短的合并到树T中；,直至X中所有顶点都在T中。,Prim算法。,2014年春季 通信网络理论基础,一个例子,24 / 50,不是最优解。,仍然不是最优解。,结论：SPH算法不能保证最优解。,2014年春季 通信网络理论基础,基于最小生成树的求解思路,25 / 50,先计算最小生成树，然后裁剪掉没用的分支 （或者只保留有用的分支）。,仍然不是最优解。,2014年春季 通信网络理论基础,26 / 50,应用：负载平衡的路由,尽量让各链路上的资源被平均使用。,用户角度：尽量避免拥塞。,网络角度：尽量减少投资浪费。,路由时，尽量避免使用负载
7、重的链路。,基于最短路：按照负载大小来决定边的权重；,基于最小生成树：给定s和d，计算从s到d的最小生成树 （以负载为权重）上的路径。,因为树上路径是最大负载最小的路径。,割最优条件。,ae, 1,ce, 1,be, 5,边上数值代表带宽,2014年春季 通信网络理论基础,27 / 50,最小生成树算法小结,Prim算法和SPH算法非常相似。都 采用了贪婪设计思想，为什么一个 可以得到最优解，而另一个却不行？ 请思考并体会贪婪思想的特点。,参考Prim算法，可以设计出SPH算 法。那么参考Kruskal算法，能否也 设计出一个Steiner树的近似解法？,2014年春季 通信网络理论基础,28
8、 / 50,树与流,关于流的算法都比较困难，属于高级论题。这里仅介绍其中最容易理解的部分。,2014年春季 通信网络理论基础,29 / 50,最大流算法,4,最大流问题,1,2,3,5,剩余网络,Ford-Fulkerson算法,两种增广路径算法,Preflow-Push算法,2014年春季 通信网络理论基础,最大流问题,30 / 50,流的大小。,流量守恒约束。,链路/边容量约束。,约束优化/数学规划,目标函数 优化目标,约束,解变量,解,线性规划,线性规划,2014年春季 通信网络理论基础,例子,31 / 50,2014年春季 通信网络理论基础,32 / 50,最大流算法,4,最大流问题,
9、1,2,3,5,剩余网络,Ford-Fulkerson算法,两种增广路径算法,Preflow-Push算法,2014年春季 通信网络理论基础,直觉,33 / 50,20,0,虽然可用线性规划方法求解，但我们将主要就其物理意义讨论解法。,我们找到s到t的路径p，看它能运送 多少流到t；然后一直这样找下去， 直到没有可以运送流的路径为止。,是的。只要按照最小容量来决定整 个路径的运送量就可以保证这两个 约束。也就是说，可以保证每次得 到的都是可行解。,0,0,0,0,20,20,想象：从b向a“反向推送” 10个单位，让它经a直接到t； 然后从s经b到t再运送10个 单位的流。流：2030,10,
10、10,10,允许“反向推送”；目的是可以“修正”以前的步骤中寻得的路径。,2014年春季 通信网络理论基础,剩余网络,34 / 50,剩余网络（Residual Network）。,rij = uij xij,rji = xij,rij: (i,j)的剩余容量,20,0,0,0,0,0,20,20,10,10,10,允许“反向推送”；目的是可以“修正”以前的步骤中寻得的路径。,2014年春季 通信网络理论基础,35 / 50,最大流算法,4,最大流问题,1,2,3,5,剩余网络,Ford-Fulkerson算法,两种增广路径算法,Preflow-Push算法,2014年春季 通信网络理论基础,
11、Ford-Fulkerson算法,36 / 50,增广路径,即增广路径上各边上剩余 容量rij 的最小值。,剩余网络中不存在 增广路径了。,2014年春季 通信网络理论基础,最大流最小割,37 / 50,原图中的某个s-t 割的容量被用光了。,2014年春季 通信网络理论基础,增广路径的选择问题,38 / 50,如果容量的取值是整数或有理数，该算法不仅一定在有限步骤内终止， 而且终止时得到的一定是最大流。这种情况下，算法复杂度为O(nmU)。,如果容量的取值不做限制，该算法既不能保证在有限步骤内终止，也 不能保证终止时得到的是最大流。,s,1,2,t,M,M,M,M,1,M 1,1,M 1,1
12、,M 1,1,M 1,1,2M次增广之后,只需要两次增广。,最大容量增广路径,最短增广路径,2014年春季 通信网络理论基础,39 / 50,最大流算法,4,最大流问题,1,2,3,5,剩余网络,Ford-Fulkerson算法,两种增广路径算法,Preflow-Push算法,2014年春季 通信网络理论基础,剩余网络,40 / 50,每次都选择最大容量的路径进行增广，可以大大减少迭代次数。,选择容量“足够大”的路径来增广。,每次设一个门限，删除所有容量小于的边。,称为剩余网络，G(x, )。,G(x),G(x, ), = 8,2014年春季 通信网络理论基础,Capacity Scaling
13、算法,41 / 50,2014年春季 通信网络理论基础,最短增广路径算法,42 / 50,跳数最小。,最短增广路径算法：每次都选择最小跳数的路径进行增广。,设每条边的权重为1，然后调用Dijkstra算法。,Better：用广度优先搜索。,因为BFS更快。,因为BFS不用FindMin。,2014年春季 通信网络理论基础,算法伪码,43 / 50,2014年春季 通信网络理论基础,44 / 50,最大流算法,4,最大流问题,1,2,3,5,剩余网络,Ford-Fulkerson算法,两种增广路径算法,Preflow-Push算法,2014年春季 通信网络理论基础,Preflow-Push算法原
14、理,45 / 50,增广路径方法的缺陷：多条增广路径可能经过同样的链路，但却必须分别进行增广操作。,10条。,每次增广多少流量？,有几条增广路径？,每次都会在前8条边上重复 地增广1个单位的流量。,能不能一次性地将流量增广到节点9，然后再从节点9 继续向后面的边上增广？,Preflow-push的思想。,Preflow-Push的基本思想：,直至没有active节点为止。,首先将尽可能多的流从源节点 “push”到邻接点去。,针对每个active节点，将多余的流量“push”到其邻接点去。,这样岂不是会导致邻接点流量不守恒？,是的。节点i的多余量excess定义为：,若e(i) 0，则节点 i
15、 称为active。,哪些“邻接点”？,如果active节点没有admissible边呢？,显然应该是“离目的点更近的”,怎样判定？,Distance Label,所有Label较小的邻接点么？,不，为了有效利用剩余容量，只选择admissible边：边ij，d(i) d(j) = 1且rij 0,假如一开始发出的流量大于实际的最大流，会发生什么？,最终，多余流量会回到源点。,Relabel：d(i) = min d(j) + 1; (i, j) A(i)且rij 0 ,确保得到新的admissible边。,假如rbt = 0?,Relabel,想象一个排水管道组成的网络。,2014年春季 通信网络理论基础,Preflow-Push算法实现,46 / 50,1,3,2,4,4,2,3,5,1,e(4)=0,e(1)=0,d(3)=1,d(1)=2,d(2)=1,d(4)=0,2,1,4,d(1)=4,e(3)=4,e(2)=2,e(2)=1,e(4)=1,e(4)=5,e(3)=0,d(2)=2,e(3)=1,e(2)=0,e(4)=6,e(3)=0,当存在多个active节点时，应该按照什么方式来选择？,FIFO preflow-push算法,Highest-label preflow-push算法,按照先
