06-树与流-XXXX-BIG

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2012,年春季,图算法及其在通信网络中的应用,#,/ 40,单击此处编辑母版标题样式,通信网络理论基础,王晟,博士 教授 博导,Part 06:,树与流,2014年春季,通信网,络,络理论,基,基础,2/ 50,树与流,1,最小生,成,成树算,法,法,最小生,成,成树的,各,各种解,法,法突出,地,地显示,了,了贪婪,算,算法的,力,力量。,2,最大流算法,3/ 50,最小生,成,成树算,法,法,Prim,算法,请着重,体,体会：,最,最优条,件,件与算,法,法的关,系,系.,Sollin,算法,Kruskal,算法,割最优条件,路径最优条件,采用类,似,似思路,二者等价,SPH,算法,综合了,两,两个算,法,法的思,路,路,2014年春季,通信网,络,络理论,基,基础,4/ 50,最小生,成,成树算,法,法,4,最优性,条,条件,1,2,3,5,Kruskal算法,Prim算法,Sollin算法,Steiner树问题,2014年春季,通信网,络,络理论,基,基础,路径最,优,优条件,5/ 50,1,2,3,4,5,6,9,10,7,8,事实,对每条非树上边,e(k,l),，,都,必然存在唯一一条,由树上边构成的,路径,p(k,l,),连接顶点,k,和顶点,l,。,：树上边,：非树上边,路径最优条件,一棵生成树为最小生成树的充要条件是：任一,非树上边,的权重都大于它所对应的树上路径上的每条边的权重。,2014年春季,通信网,络,络理论,基,基础,树上边与,割,割集,6/ 50,1,2,3,4,5,6,9,10,7,8,：树上边,：非树上边,S2,S1,割集,删除任意一条树上边,e(i,j),，,都会,将原图划分,为两,个,部,分,。,原图中连接这两个部分的,边,（,包括树上边和,非树,上边,）,的,集合，称为割集。,事实,每条树上边,e(i,j),都对应一个割集。,2014年春季,通信网,络,络理论,基,基础,割最优,条,条件,7/ 50,一棵生成树为最小生成树的充要条件是：任一,树上边,的权重都小于它所对应的割集中每条边的权重。,割最优条件,1,2,3,4,5,6,9,10,7,8,S2,S1,事实,每条树上边,e(i,j),都,对应,一个割集。,：树上边,：非树上边,2014年春季,通信网,络,络理论,基,基础,8/ 50,最小生,成,成树算,法,法,4,最优性,条,条件,1,2,3,5,Kruskal算法,Prim算法,Sollin算法,Steiner树问题,2014年春季,通信网,络,络理论,基,基础,从最优,条,条件到,算,算法,9/ 50,路径最优条件,从一棵生成树开始，检查其非树上边；,一旦发现最优条件被违背，则替换；,直至所有的非树上边都满足该条件。,不能保证多项式时间。,请通过,Kruskal,的思想来体会一下数据结构在算法设计中的重要性。,2014年春季,通信网,络,络理论,基,基础,10/ 50,Kruskal算法思,想,想,若该边的两个端点属于不同的树，就合并这两棵树；,若属于同一棵树，就删除该边，继续检查；,把原图中所有边按权重的升序排序；,一开始把原图看作一个森林，含,n,棵树；,按序、逐条地检查边：,直至只剩下一棵树（,或者留下来的,边的数目为,n1,）。,为啥不检查完所有的边？,剩下没检查的边都必然是非树上边，且权重更大。,2014年春季,通信网,络,络理论,基,基础,路径最,优,优条件,在,在哪里,？,？,11/ 50,跟路径最优条件有啥关系？,Kruskal,算法中被排除的边是什么样的边？,是那种两个端点已经在同一,树上,的边。即非树上边。,根据路径最优条件，什么时候应该排除非树上边,e(i,j),？,当树上路径,P(i,j),中的每条边,的权重,都小于,e(i,j),时。,Kruskal,算法中，为啥不用做这样的比较？,因为所有的边已排序。,结论：由于路径最优条件，所以,Kruskal,算法是正确的。,2014年春季,通信网,络,络理论,基,基础,一个例,子,子,12/ 50,b,a,c,d,35,25,e,40,20,10,15,30,b,a,c,d,e,10,15,20,35,2014年春季,通信网,络,络理论,基,基础,Kruskal算法实,现,现,13/ 50,怎样检查边是否属于树？,怎样进行树的归并？,每棵树都用一个顶点的,list,来表达，并记录该,list,的,size,和,last,。,每个顶点都附加一个变量,first,，用于记录该顶点所在的,list,的第一个顶点。,数据结构设计,请再次体会数据结构的力量：采用下述数据结构设计后，复杂度从,O(nm),降为,O(m+nlogn),。,怎样检查边是否属于树？,看,两个顶点的,first,是否相同。,怎样进行树的归并？,比较,size,；将较小的树插入,到,较大,的树后面（,last,）。,为什么要把大的放在前面？,因为排在后面的,list,中的,顶点,都,要更新其,first,值。,2014年春季,通信网,络,络理论,基,基础,14/ 50,最小生,成,成树算,法,法,4,最优性,条,条件,1,2,3,5,Kruskal算法,Prim算法,Sollin算法,Steiner树问题,2014年春季,通信网,络,络理论,基,基础,Prim算法,15/ 50,路径最优条件,割最优条件,Kruskal算法,Prim算法,基本思想：从某个顶点（初始树）出发，一次增加一条边到树上，直至最后。,哪个顶点？,随便哪个都行。,哪条边？,假定已在树上的顶点,集合,为,S,，那么,每次,循环中,得到,的,S,和,VS,就定义了,原图的,一,种划分。,对应这种划分，必有一个割集。,根据割最优条件，应该选该,割,集中权重最小,的边。,b,a,c,d,35,25,e,40,20,10,15,30,2014年春季,通信网,络,络理论,基,基础,Prim算法伪,码,码,16/ 50,FOR all vertex j in V DO,d(j) =,; p(j) = NULL;,S = s; d(s) = 0; p(s) = NULL;,Update(s);,WHILE S, V DO,i = FindMin();,S = S U i;,Update(i);,END WHILE,Update ( i ),FOR each edge e incident to i DO,IF e.weight + d(i) d(e.head) THEN,d(e.head) = e.weight + d(i);,p(e.head) = i;,END IF,END FOR,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,和,Prim,两个算法的综合。,基本思想：,从森林开始，通过合并树最终求得生成树；,合并时，总是挑选最小权重的割边。,Kruskal,算法,Prim,算法,2014年春季,通信网,络,络理论,基,基础,Sollin算法伪,码,码,19/ 50,FOR all vertex j in V DO,N(j) = j,;,T* =,;,WHILE T*.size (n 1),DO,FOR each tree N(k) DO,nearest_neighbor(N(k), ik, jk);,FOR each tree N(k) DO,IF ik,和,jk,属于不同的树,THEN,merge(ik, jk);,T,* = T* (ik,jk);,END WHILE,Sollin,Alg,( G(V,E) ),查找,N(k),与,V N(k,),之间,的最小割,边：,(,ik, jk),将,ik,和,jk,所属于,的,树,合并,起来。,2014年春季,通信网,络,络理论,基,基础,一个例,子,子,20/ 50,FOR all vertex j in V DO,N(j) = j,;,T* =,;,WHILE T*.size 0,且,d(j)=FALSE THEN,p(j) = i; d(j) = TRUE,;,LIST = LIST,U j;,END WHILE,IF d(t) THEN,确定,s,到,t,的增广路径,p,；,确定,p,的增广容量,d*;,沿着路径,p,输送,d*,单位的流,;,更新,图,G(x),中各边上的,r,ij,;,END WHILE,Shortest_Augmenting_Path( G(V,E), s, t,),2014年春季,通信网,络,络理论,基,基础,44/ 50,最大流,算,算法,4,最大流,问,问题,1,2,3,5,剩余网,络,络,Ford-Fulkerson算法,两种增,广,广路径,算,算法,Preflow-Push算法,2014年春季,通信网,络,络理论,基,基础,Preflow-Push算法原,理,理,45/ 50,增广路径方法的缺陷：多条增广路径可能经过同样的链路，但却必须分别进行增广操作。,10,条。,每次增广多少流量？,有几条增广路径？,每次都会在前,8,条边上,重复,地,增广,1,个单位的流量。,能不能,一次性地,将流量增广到节点,9,，然后再从节点,9,继续向后面的边上增广？,Preflow-push,的思想。,Preflow-Push,的基本思想：,直至没有,active,节点为止。,首先将尽可能多的流从源节点,“,push,”到邻接点去。,针对每个,active,节点，将多余的流量“,push,”到其邻接点去。,这样岂不是会导致邻接点流量不守恒？,是的。节点,i,的多余量,excess,定义为：,若,e,(,i,), 0,，则节点,i,称为,active,。,哪些“邻接点”？,如果,active,节点没有,admissible,边呢？,显然应该是“离目的点,更近,的”,怎样判定？,Distance,Label,所有,Label,较小的邻接点么？,不，为了有效利用剩余容量，只选择,admissible,边：边,i,j,，,d,(,i,),d,(,j,) = 1,且,r,ij, 0,假如一开始发出的流量大于实际的最大流，会发生什么？,最终，多余流量会回到源点。,Relabel,：,d,(,i,) = min,d,(,j,) + 1; (,i,j,),A,(,i,),且,r,ij, 0,确保得到新的,admissible,边。,a,t,c,d,b,2,1,1,5,s,2,1,0,假如,r,bt,= 0?,Relabel,a,t,c,d,b,2,1,3,1,5,s,2,1,0,想象一个排水管道组成的网络。,2014年春季,通信网,络,络理论,基,基础,Preflow-Push算法实,现,现,46/ 50,Preprocess,;,WHILE,网络中还有,active,节点,DO,选择一个,active,节点,i,;,Push-and-relabel,(,i,);,END WHILE,Preflow-push(,G(V,E), s, t,),x,: = 0;,计算距离标记,d,(,i,);,x,sj,:=,u,sj,for each arc (,s,j,),A,(,s,);,d,(,s,) :=,N,; /,N,为节点数目,Preprocess,IF,存在,admissible,边,(,i,j,) THEN,:= min,e,(,i,),r,ij,；,从,i,向,j,push,个单位的流；,ELSE,d,(,i,) := min,d,(,j,) + 1: (,i,j,),A,(,i,),and,r,ij, 0 ;,Push-and-relabel(,i,),1,3,2,4,4,2,3,5,1,e(4,),)=0,r,ij,e(1,),)=0,d(3,),)=1,d(1,),)=2,d(2,),)=1,d(4,),)=0,1,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,算法,按照先入先出顺序选择,按照,Label,大小选择,研究性,Project No. R3,实现并,比较三种算法,的性能（速度,）,最短增广路径；,FIFO,preflow-push,；,Highest-label,preflow-push,。,2014年春季,通信网,络,络理论,基,基础,最大流,算,算法应,用,用（一,）,）,47/ 50,什么叫通信网络的可靠性？,我们这里定义为任意两个顶点,间链路,分离的路径的数目。,这跟最大流有啥关系？,若边,的容量都设为,1,，流也,必须是,整数。求得的最大,流值是什么？,就是可靠性。,应用之一：,通信网络的可靠性,2014年春季,通信网,络,络理论,基,基础,最大流,算,算法应,用,用（二,）,）,48/ 50,什么叫通信网络的关键链路？,如何确定两个顶点之间的最小割？,如果,e1,同时包含在,(a,b),之间和,(c,d),之间,的最小,割中；而,e2,只,包含,在,(c,d),之间的,最小割,中，那么,e1,的关键性大于,e2,。,最短增广路径算法终止时，顶点被划分,为两,个部分,S,和,T,。从,S,到,T,的,边组成最小割。,应用之二：,最小干扰路由,什么,叫最小干扰路由？,减少阻塞的一种路由方法。基本思想：以链路关键度作为权重，,求解最小权重路径。,2014年春季,通信网,络,络理论,基,基础,49/ 50,最大流,算,算法小,结,结,Ford-Fulkerson,算法,Capacity Scaling,算法,最短增广路径,算法,问题定义,剩余网络,最大流最小割定理,Preflow-Push,算法,2014年春季,通信网,络,络理论,基,基础,EndofPart06,Andthe journey,