06-树与流-XXXX-BIG

通信网络理论基础王晟博士教授博导Part06:树与流2014年春季通信网络理论基础2/50树与流1最小生成树算法最小生成树的各种解法突出地显示了贪婪算法的力量。2最大流算法3/50最小生成树算法Prim算法请着重体会：最优条件与算法的关系.Sollin算法Kruskal算法割最优条件路径最优条件采用类似思路二者等价SPH算法综合了两个算法的思路2014年春季通信网络理论基础4/50最小生成树算法4最优性条件1235Kruskal算法Prim算法Sollin算法Steiner树问题2014年春季通信网络理论基础路径最优条件5/5012345691078事实对每条非树上边e(k,l)，都必然存在唯一一条由树上边构成的路径p(k,l)连接顶点k和顶点l。：树上边：非树上边路径最优条件一棵生成树为最小生成树的充要条件是：任一非树上边的权重都大于它所对应的树上路径上的每条边的权重。2014年春季通信网络理论基础树上边与割集6/5012345691078：树上边：非树上边S2S1割集删除任意一条树上边e(i,j)，都会将原图划分为两个部分。原图中连接这两个部分的边（包括树上边和非树上边）的集合，称为割集。事实每条树上边e(i,j)都对应一个割集。2014年春季通信网络理论基础割最优条件7/50一棵生成树为最小生成树的充要条件是：任一树上边的权重都小于它所对应的割集中每条边的权重。割最优条件12345691078S2S1事实每条树上边e(i,j)都对应一个割集。：树上边：非树上边2014年春季通信网络理论基础8/50最小生成树算法4最优性条件1235Kruskal算法Prim算法Sollin算法Steiner树问题2014年春季通信网络理论基础从最优条件到算法9/50路径最优条件从一棵生成树开始，检查其非树上边；一旦发现最优条件被违背，则替换；直至所有的非树上边都满足该条件。不能保证多项式时间。请通过Kruskal的思想来体会一下数据结构在算法设计中的重要性。2014年春季通信网络理论基础10/50Kruskal算法思想若该边的两个端点属于不同的树，就合并这两棵树；若属于同一棵树，就删除该边，继续检查；把原图中所有边按权重的升序排序；一开始把原图看作一个森林，含n棵树；按序、逐条地检查边：直至只剩下一棵树（或者留下来的边的数目为n–1）。为啥不检查完所有的边？剩下没检查的边都必然是非树上边，且权重更大。2014年春季通信网络理论基础路径最优条件在哪里？11/50跟路径最优条件有啥关系？Kruskal算法中被排除的边是什么样的边？是那种两个端点已经在同一树上的边。即非树上边。根据路径最优条件，什么时候应该排除非树上边e(i,j)？当树上路径P(i,j)中的每条边的权重都小于e(i,j)时。Kruskal算法中，为啥不用做这样的比较？因为所有的边已排序。结论：由于路径最优条件，所以Kruskal算法是正确的。2014年春季通信网络理论基础一个例子12/50bacd3525e4020101530bacde101520352014年春季通信网络理论基础Kruskal算法实现13/50怎样检查边是否属于树？怎样进行树的归并？•每棵树都用一个顶点的list来表达，并记录该list的size和last。•每个顶点都附加一个变量first，用于记录该顶点所在的list的第一个顶点。数据结构设计请再次体会数据结构的力量：采用下述数据结构设计后，复杂度从O(nm)降为O(m+nlogn)。怎样检查边是否属于树？看两个顶点的first是否相同。怎样进行树的归并？比较size；将较小的树插入到较大的树后面（last）。为什么要把大的放在前面？因为排在后面的list中的顶点都要更新其first值。2014年春季通信网络理论基础14/50最小生成树算法4最优性条件1235Kruskal算法Prim算法Sollin算法Steiner树问题2014年春季通信网络理论基础Prim算法15/50路径最优条件割最优条件Kruskal算法Prim算法基本思想：从某个顶点（初始树）出发，一次增加一条边到树上，直至最后。哪个顶点？随便哪个都行。哪条边？假定已在树上的顶点集合为S，那么每次循环中得到的S和V–S就定义了原图的一种划分。对应这种划分，必有一个割集。根据割最优条件，应该选该割集中权重最小的边。bacd3525e40201015302014年春季通信网络理论基础Prim算法伪码16/50FORallvertexjinVDOd(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)2014年春季通信网络理论基础17/50最小生成树算法4最优性条件1235Kruskal算法Prim算法Sollin算法Steiner树问题2014年春季通信网络理论基础Sollin算法18/50Sollin算法可以看作是Kruskal和Prim两个算法的综合。基本思想：从森林开始，通过合并树最终求得生成树；合并时，总是挑选最小权重的割边。Kruskal算法Prim算法2014年春季通信网络理论基础Sollin算法伪码19/50FORallvertexjinVDON(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所属于的树合并起来。2014年春季通信网络理论基础一个例子20/50FORallvertexjinVDON(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))bacd3525e4020101530bacde35101510152020351020152014年春季通信网络理论基础21/50最小生成树算法4最优性条件1235Kruskal算法Prim算法Sollin算法Steiner树问题2014年春季通信网络理论基础Steiner树问题22/50施泰纳(Steiner)树问题给定加权图G，以及一个V的子集X，求一棵包含了X中所有顶点的，最小权重的树。与最小生成树的区别与联系：同样是求最小权重的树。不必覆盖所有顶点。但是可以利用所有的顶点来构造树。2014年春季通信网络理论基础SPH算法23/50ShortestPathHeuristic(SPH)的基本思想：求X中各个顶点对之间的最短路，其中最短的作为初始树T；求X中其他顶点到T的最短路，把其中最短的合并到树T中；直至X中所有顶点都在T中。跟哪个最短路算法很像？从一棵初始树开始。Prim算法。每次添加一个点到树上。添加哪个点？离当前树最近的点。2014年春季通信网络理论基础一个例子24/50bacd4e1212434X={bcd}假如初始树选为e(d,c)呢？不是最优解。bacd4e3233454X={bcd}只是初始树的选择问题么？仍然不是最优解。结论：SPH算法不能保证最优解。2014年春季通信网络理论基础基于最小生成树的求解思路25/50由于Steiner树问题与最小生成树问题的相似性，很容易想到这样的求解思路：先计算最小生成树，然后裁剪掉没用的分支（或者只保留有用的分支）。bacd4e3333444X={bcd}生成树是什么？裁剪后呢？最优解呢？仍然不是最优解。该算法和SPH都是近似解，谁的性能更好？2014年春季通信网络理论基础26/50应用：负载平衡的路由什么叫负载平衡的路由？尽量让各链路上的资源被平均使用。为什么需要负载平衡？用户角度：尽量避免拥塞。网络角度：尽量减少投资浪费。怎样实现？路由时，尽量避免使用负载重的链路。基于最短路：按照负载大小来决定边的权重；基于最小生成树：给定s和d，计算从s到d的最小生成树（以负载为权重）上的路径。为什么用树上路径？因为树上路径是最大负载最小的路径。为什么！？割最优条件。ae,1ce,1be,5bacde642245边上数值代表带宽2014年春季通信网络理论基础27/50最小生成树算法小结最小生成树•两个最优条件和三个算法的关系。•三个算法的设计思想。•数据结构的选择技巧。•与最小生成树问题的关系。•SPH算法的设计思想。Steiner树思考题Prim算法和SPH算法非常相似。都采用了贪婪设计思想，为什么一个可以得到最优解，而另一个却不行？请思考并体会贪婪思想的特点。参考Prim算法，可以设计出SPH算法。那么参考Kruskal算法，能否也设计出一个Steiner树的近似解法？2014年春季通信网络理论基础28/50树与流1最小生成树算法关于流的算法都比较困难，属于高级论题。这里仅介绍其中最容易理解的部分。2最大流算法2014年春季通信网络理论基础29/50最大流算法4最大流问题1235剩余网络Ford-Fulkerson算法两种增广路径算法Preflow-Push算法2014年春季通信网络理论基础最大流问题30/50Maximizev=SjxsjSubjecttoSjxij－Skxki=0foreachis,t0xijuijforall(i,j)E.最大流问题符号说明:给定图G(V,E)xij:边(i,j)上的流uij:边(i,j)上的容量s:源顶点t:宿顶点要求最大化的是什么？第一个约束是什么？第二个约束是什么？流的大小。流量守恒约束。链路/边容量约束。约束优化/数学规划目标函数优化目标约束解变量解线性规划线性规划2014年春季通信网络理论基础例子31/50s12t10,88,71,110,66,5可行解：满足所有约束的解。最优解：满足所有约束且使得目标函数达到最优的解。是最优解么？Maximizev=SjxsjSubjecttoSjxij－Skxki=0foreachis,t0xijuijforall(i,j)E.最大流问题是可行解么？该例中最优解是什么？2014年春季通信网络理论基础32/50最大流算法4最大流问题1235剩余网络Ford-Fulkerson算法两种增广路径算法Preflow-Push算法2014年春季通信网络理论基础直觉33/5020sabt20103020100虽然可用线性规划方法求解，但我们将主要就其物理意义讨论解法。直觉：我们找到s到t的路径p，看它能运送多少流到t；然后一直这样找下去，直到没有可以运送流的路径为止。这样能保证容量和流守恒约束么？是的。只要按照最小容量来决定整个路径的运送量就可以保证这两个约束。也就是说，可以保证每次得到的都是可行解。00002020找不到路了怎么办？想象：从b向a“反向推送”10个单位，让它经a直接到t；然后从s经b到t再运送10个单位的流。流：2030101010改进的直觉：允许“反向推送”；目的是可以“修正”以前的步骤中寻得的路径。2014年春季通信网络理论基础剩余网络34/50找路的过程中，怎样才能得到这样的解？剩余网络（ResidualNetwork）。ijxijuijijrij=uij–xijrji=xijrij:(i,j)的剩