通信网络理论基础-树与流-2013

通信网理论基础虞红芳教授博导Part06:树与流2/32树与流1最小生成树算法最小生成树的各种解法突出地显示了贪婪算法的力量。2最大流算法2013年春季3/32最小生成树算法4最优性条件1235Kruskal算法Prim算法Sollin算法Steiner树问题2013年春季2013年春季4/32最优性条件12345691078：树上边：非树上边事实对每条非树上边e(k,l)，都必然存在唯一一条由树上边构成的路径p(k,l)连接顶点k和顶点l。S2S1割集删除任意一条树上边e(i,j)，都会将原图顶点划分为两个部分。原图中连接这两个部分的边（包括树上边和非树上边）的集合，称为割集。事实每条树上边e(i,j)都对应一个割集。路径最优条件一棵生成树为最小生成树的充要条件是：任一非树上边的权重都大于它所对应的树上路径上的每条边的权重。一棵生成树为最小生成树的充要条件是：任一树上边的权重都小于它所对应的割集中每条边的权重。割最优条件5/32最小生成树算法Prim算法请着重体会：最优条件与算法的关系.Sollin算法Kruskal算法割最优条件路径最优条件采用类似思路二者等价SPH算法综合了两个算法的思路2013年春季6/32最小生成树算法4最优性条件1235Kruskal算法Prim算法Sollin算法Steiner树问题2013年春季7/32Kruskal算法思想路径最优条件从一棵生成树开始，检查其非树上边；一旦发现最优条件被违背，则替换；直至所有的非树上边都满足该条件。不能保证多项式时间。请通过Kruskal的思想来体会一下数据结构在算法设计中的重要性。若该边的两个端点属于不同的树，就合并这两棵树；若属于同一棵树，就删除该边，继续检查；把原图中所有边按权重的升序排序；一开始把原图看作一个森林，含n棵树；按序、逐条地检查边：直至只剩下一棵树（或者剩下的边的数目为n–1）。跟路径最优条件有啥关系？Kruskal算法中被排除的边是什么样的边？是那种两个端点已经在同一树上的边。即非树上边。根据路径最优条件，什么时候应该排除非树上边e(i,j)？当树上路径P(i,j)中的每条边的权重都小于e(i,j)时。Kruskal算法中，为啥不用做这样的比较？因为所有的边已排序。结论：由于路径最优条件，所以Kruskal算法是正确的。为啥不检查完所有的边？2013年春季8/32Kruskal算法实现bacd3525e4020101530bacde10152035怎样检查边是否属于树？怎样进行树的归并？•每棵树都用一个顶点的list来表达，并记录该list的size和last。•每个顶点都附加一个变量first，用于记录该顶点所在的list的第一个顶点。数据结构设计请再次体会数据结构的力量：采用下述数据结构设计后，复杂度从O(nm)降为O(m+nlogn)。怎样检查边是否属于树？太容易了！看两个顶点的first是否相同。怎样进行树的归并？比较size；将较小的树插入到较大的树后面（last）。为什么要把大的放在前面？因为排在后面的list中的顶点都要更新其first值。2013年春季9/32最小生成树算法4最优性条件1235Kruskal算法Prim算法Sollin算法Steiner树问题2013年春季10/32Prim算法路径最优条件割最优条件Kruskal算法Prim算法基本思想：从某个顶点（初始树）出发，一次增加一条边到树上，直至最后。哪个顶点？哪条边？随便哪个都行。假定已在树上的顶点集合为S，那么每次循环中得到的S和V–S就定义了原图的一种划分。对应这种划分，必有一个割集。根据割最优条件，应该选该割集中权重最小的边。bacd3525e4020101530FORallvertexjinVDOd(j)=;p(j)=NULL;S={s};d(s)=0;p(s)=NULL;Update(s);WHILESVDOi=FindMin();S=SU{i};Update(i);ENDWHILEUpdate(i)FOReachedgeeincidenttoiDOIFe.weight+d(i)d(e.head)THENd(e.head)=e.weight+d(i);p(e.head)=i;ENDIFENDFORDijkstraAlg(G(V,E),s)PrimAlg(G(V,E),s)2013年春季11/32最小生成树算法4最优性条件1235Kruskal算法Prim算法Sollin算法Steiner树问题2013年春季12/32Sollin算法Sollin算法可以看作是Kruskal和Prim两个算法的综合。基本思想：从森林开始，通过合并树最终求得生成树；合并时，总是挑选最小权重的割边。Kruskal算法Prim算法FORallvertexjinVDON(j)={j};T*=;WHILET*.size(n–1)DOFOReachtreeN(k)DOnearest_neighbor(N(k),ik,jk);FOReachtreeN(k)DOIFik和jk属于不同的树THENmerge(ik,jk);T*=T*∪{(ik,jk)};ENDWHILESollinAlg(G(V,E))查找N(k)与V–N(k)之间的最小割边，(ik,jk)将ik和jk所属于的树合并起来2013年春季13/32Sollin算法FORallvertexjinVDON(j)={j};T*=;WHILET*.size(n–1)DOFOReachtreeN(k)DOnearest_neighbor(N(k),ik,jk);FOReachtreeN(k)DOIFik和jk属于不同的树THENmerge(ik,jk);T*=T*∪{(ik,jk)};ENDWHILESollinAlg(G(V,E))bacd3525e4020101530bacde35101510152020351020152013年春季14/32最小生成树算法4最优性条件1235Kruskal算法Prim算法Sollin算法Steiner树问题2013年春季15/32Steiner树问题与SPH施泰纳(Steiner)树问题给定加权图G，以及一个V的子集X，求一棵包含了X中所有顶点的，最小权重的树。ShortestPathHeuristic(SPH)的基本思想：求X中各个顶点对之间的最短路，其中最短的作为初始树T；求X中其他顶点到T的最短路，把其中最短的合并到树T中；直至X中所有顶点都在T中。bacd4e1212434X={bcd}假如初始树选为e(d,c)呢？不是最优解。bacd4e3233454X={bcd}只是初始树的选择问题么？仍然不是最优解。结论：SPH算法不能保证最优解。2013年春季16/32基于最小生成树裁剪由于Steiner树问题与最小生成树问题的相似性，很容易想到这样的求解思路：先计算最小生成树，然后裁剪掉没用的分支（或者只保留有用的分支）。bacd4e3333444X={bcd}生成树是什么？裁剪后呢？最优解呢？不是最优解。该算法和SPH都是近似解，谁的性能更好？2013年春季17/32应用：负载平衡的路由什么叫负载平衡的路由？尽量让网络中各链路上的资源被平均使用。为什么需要负载平衡？用户角度：尽量避免拥塞。网络角度：尽量减少投资浪费。怎样实现？路由时，尽量避免使用负载重的链路。基于最短路：按照负载大小来决定边的权重；基于最小生成树：给定s和d，计算从s到d的最小生成树（以负载为权重）上的路径。为什么用树上路径？因为树上路径是最大负载最小的路径。为什么！？割最优条件。ae,1ce,1be,5bacde642245边上数值代表带宽2013年春季18/32最小生成树算法小结最小生成树•两个最优条件和三个算法的关系。•三个算法的设计思想。•数据结构的选择技巧。•与最小生成树问题的关系。•SPH算法的设计思想。Steiner树思考题Prim算法和SPH算法非常相似。都采用了贪婪设计思想，为什么一个可以得到最优解，而另一个却不行？请思考并体会贪婪思想的特点。参考Prim算法，可以设计出SPH算法。那么参考Kruskal算法，能否也设计出一个Steiner树的近似解法？2013年春季19/32树与流1最小生成树算法关于流的算法都比较困难，属于高级论题。这里仅介绍其中最容易理解的部分。2最大流算法2013年春季20/32最大流算法4最大流问题1235剩余网络Ford-Fulkerson算法两种增广路径算法Preflow-Push算法2013年春季21/35基本术语：流2/2/5OSQRPT3/3/22/2/52/3/23/3/43/3/30/2/11/4/2关于流(Flow)的描述性定义•一般，flow定义在流网络(flownetwork)上的一对顶点(s,t)之间，称为(s,t)流。其中s为流的起始点，t为流的终止点。•流网络的每条边上都有容量(Capacity)；有的流问题中还要定义单位单价(Cost)。•在每条边上，流都必须满足容量约束。•在流经过的每个节点(除了s和t)上，流都需要满足守恒原则。s只有流出的流，t只有流入的流。•s流出的总和(或t流入的总和)定义为流的大小。•每条边上流量与代价相乘，然后对所有边求和，就得到流的代价。S为源，T为目的。边上的x/y/z，x代表流量值，y代表容量，z代表代价。满足容量约束么？满足流量守恒么？流的大小？流的代价？5532013年春季22/35最大流问题MaximumFlowProblem给定流网络G，给定节点对(s,t)，求从s到t的一个流，使得流量值最大(或者只要求得到最大流量值)。?/2OSQRPT?/3?/2?/3?/3?/3?/2?/4?/1OSQRPT?/1?/1?/1?/1?/1?/1?/1(S,T)之间的最大流？将每条边上的容量都设置为1，求(S,T)之间的最大流(要求必须是整数)？2013年春季23/35最小费用流问题MinimumCostFlowProblem给定流网络G，给定节点对(s,t)，以及s到t的流量需求x，求一个流量安排方案(即一个流)，该流的大小为x，且是所有大小为x的流中，代价最小的。(S,T)之间的流量需求为3。求最小费用流。每条边上的容量都设置为1，(S,T)之间需求也为1，求出的最小费用流是什么？?/2/5OSQRPT?/3/2?/2/5?/3/2?/3/4?/3/3?/2/1?/4/2?/1/5OSQRPT?/1/2?/1/5?/1/2?/1/4?/1/3?/1/1?/1/22013年春季25/32剩余网络20sabt20103020100我们将主要就其物理意义来展开讨论。直觉：我们找到s到t的路径p，看它能运送多少流到t；然后一直这样找下去，直到没有可以运送流的路径为止。这样能保证容量和流守恒约束么？是的。只要按照最小容量来决定整个路径的运送量就可以保证这两个约束。也就是说，可以保证每次得到的都是可行解。00002020找不到路了怎么办？想象：从b向a“反向推送”10个单位，让它经a直接到t；然后从s经b到t再运送10个单位的流。流：2030101010找路的过程中，怎样才能得到这样的解？剩余网络（ResidualNetwork）。ijxijuijijrij=uij–xijrji=xijrij:(i,j)的剩余容量sabt20103020102000000bsat202020201020101010101010202013年春季26/32最大流算法4最大流问题1235剩余网络Ford-Fulkerson算法两种增广路径算法Preflow-Push算法2013年春季27/32Ford-Fulkerson算法(一)x:=0;构建剩余网络G(x);WHILEG(x)中存在s到t的路径pDO确定p的增广容量d*;沿着路径p输送d*单位的流;更新图中各边上的剩余容量rij;ENDWHILEFord-Fulkerson(G(V,E),s,t)增广路径即增广路径上各边上剩余容量rij的最小值。s12t10,9