毛毛毕业论文答辩课件

河北大学2013届硕士毕业论文答辩网络最大流算法研究指导教师：毛华答辩人：毛晓亮学科专业：基础数学答辩日期：2013年5月1目录本文目录网络最大流研究背景算法改进的基础主要算法内容总结2研究背景网络最大流理论的研究至今已经有将近60年的历史，最早是Dantzig(1951)从运筹学的角度出发的网络单纯形法，随着Ford和Fulkerson（1956）标号算法的提出，由图论出发的网络流理论才被系统的建立起来。50多年来，以2F标号算法为基础，大量新颖有效的算法陆续被提出，不断丰富和完善着网络流理论，近年来，随着计算机技术的迅猛发展，最大流算法复杂度的下界不断被改进，同时，理论算法的实际实现效率不断提高，进而使网络最大流理论在信息传输，路网交通，物资调运，配送，图像处理等领域的应用越来越广泛，应用价值也越来越高。3研究背景第三，基于图论基础上的网络最大流理论，较之组合数学，运筹学上的方法，有其独有的优势，现行算法比一般的线性规划处理方法要简单很多。正是因为其简便性，因此，对于如何发现网络最大流理论的更多有价值的实际应用，本身就是一个很值得研究的重要课题。52.本文算法改进的基础第一，1956年由Ford和Fulkerson提出的2F标号算法，此算法又被称为增广路算法，即在剩余网络中不断寻找增广路，每找到一条增广路就进行一次增流，直至找到全部增广路为止。但是，对于复杂网络，增广路寻找本身就是一个极为棘手的问题，更为无奈的是，当网络的最大弧容量为无理数时，最大流不收敛。因此，2F标号算法是伪多项式算法。62.本文算法改进的基础第二，1970年到1973年，Dinic增量网络算法的提出，使得最大流算法的复杂度进一步降低，由原来的O(nm2)和O(n2m)降低到O(m2logU)和O(nmlogU),其中U为整型网络的最大弧容量。此后很长一段时间，算法时间复杂度核心因子一直停留在O(nm)，没有能被突破。73.1Dinic增量网络算法的分析1.算法的基本步骤：Step0:初始化网络的可行流f0；Step1:构造网络的增量网络N(f)；Step2:对增量网络N(f)分层，若分层不能达到汇点y，则网络的最大流为f0，否则转下步；Step3:构造网络的辅助网络AN(f)，在AN(f)中寻找x-y有向路，即可增路；Step4:沿可增路增流完毕之后，删去已经被注满的边，反复增流，直至AN(f)中不存在x-y有向路为止；Step5:循环执行以上步骤，若网络已不能分层至y点，则网络最大流已找到；93.1Dinic增量网络算法分析2.Dinic算法存在的问题：103.1Dinic增量网络算法的分析2.Dinic算法存在的问题：增广路选择的顺序不同会导致最大流的流值无法达到最优113.1Dinic增量网络算法的分析2.Dinic算法存在的问题：增广路选择的顺序不同会导致最大流的流值无法达到最优133.1Dinic增量网络算法的分析2.Dinic算法存在的问题：增广路选择的顺序不同会导致最大流的流值无法达到最优143.1Dinic增量网络算法的分析2.Dinic算法存在的问题：增广路选择的顺序不同会导致最大流的流值无法达到最优153.1Dinic增量网络算法的分析2.Dinic算法存在的问题：删去已经饱和的弧，更新网络：173.1Dinic增量网络算法的分析2.Dinic算法存在的问题：此时网络的最大流的流值为：2+2=4，而实际网络的最大流为：2+2+2=6；183.2基于枢纽度的增广路算法1.算法改进中的一些重要概念枢纽度：设网络N=(V,x,y,A,C)，任意uV,TV，T={v|其中v为u的邻点}，为了表示v点对于u点的重要程度，我们称v点的度（出度与入度之和）d(v)的倒数1/d(v)为网络的枢纽度，记为Key(v)，将枢纽度最大的点称为枢纽点。注1(1)枢纽度表示的是此点在网络连通性中的重要程度，换言之，删去此点对网络的连通性影响较大。193.2基于枢纽度的增广路算法产出比值设网络N=(V,x,y,A,C)，任意vV,为点v的任一出弧，为点v的任一入弧，其弧容量分别为，，定义称Tran(v)为v点的产出比值。注(1)由Tran(v)的定义可知，Tran(v)总是小于1的值。(2)给出一个新的标记，Impo(v)=Key(x)Tran(v)，称Impo(v)为v点的流枢纽度。213.2基于枢纽度的增广路算法Input:网络N=(V,x,y,A,C)(即初始可行流为零流的增量网络)Output:网络N的一个最大流Val.BeginVal=0;S={x};whileN中存在增广路P;dowhile(v!=y)Key(v)=为u的邻点,uS;

令Val+=223.2基于枢纽度的增广路算法更新增量网络；End仍然以原来的网络的为例：233.2基于枢纽度的增广路算法同理，第二条枢纽路：253.2基于枢纽度的增广路算法第三条枢纽路：263.3基于流枢纽度的增广路算法Input:网络N=(V,x,y,A,C).Output:网络N的一个最大流Val.BeginVal=0;S={x};whileN中存在增广路P;dowhile(v!=y)Impo(v)=maxImpo(vi),vi为u的邻点,uS;

Val+=

293.3基于流枢纽度的增广路算法End网络实例运行结果与理论值十分吻合303.3基于流枢纽度的增广路算法例3如图所示网络N=(V,x,y,A,C)：利用流枢纽度增广路算法来求解网络的最大流。313.3基于流枢纽度的增广路算法首先，初始化Val=0，S={x},考察x的邻点v1，v3，现在分别计算其枢纽度和产出比值：Key(v1)=1/4，Tran(v1)=Key(v3)=1/3，Tran(v3)=323.3基于流枢纽度的增广路算法因此，流枢纽度为：Impo(v1)=Key(v1)Tran(v1)=Impo(v3)=Key(v3)Tran(v3)=

333.3基于流枢纽度的增广路算法maxImpo(v1)=5/28，maxImpo(v3)=8/27，显然，maxImpo(v3)>maxImpo(v1)，由算法的执行过程可知，枢纽路上选择v3点，且指向v4点，依照深度优先的原则，下一个点将会标到v4，显然，第一条枢纽路为P1=xv3v4y

343.3基于流枢纽度的增广路算法同理，得到其他的流枢纽度增广路，最终得到更新后的网络：354.二分部分割矩阵算法本节算法的思想如下：首先，对于网络N=(V,x,y,A,C)，构造其逆向网络=(V,y,x,A-1,C)，同时构造出两者的部分割矩阵；其次，由连通性定理，寻找N的部分割矩阵的子阵，当子阵阶数较大时，转向求N-1的部分割矩阵的子阵；最后，对子阵进行集合的并交运算，并最终求得网络的最小割，也即，网络的最大流。364.二分部分割矩阵算法得到的几个定理：流等价定理设网络N=(V,x,y,A,C)，N

-1=(V,y,x,A-1,C),则，N与N

-1的最大流值相等。(2)连通性定理K=(S,)是N=(V,x,y,A,C)的一个割集，若G(S)不连通，则K一定不是网络N的最小割。374.二分部分割矩阵算法2.给出的一些概念：(1)(部分割容量矩阵)下面的n-1阶容量矩阵T称为网络N的部分割容量矩阵:384.二分部分割矩阵算法(2)部分割容量矩阵的特殊子阵=394.二分部分割矩阵算法网络实例：404.二分部分割矩阵算法首先，构造网络和逆向网络的部分割容量矩阵：T=414.二分部分割矩阵算法逆向网络：424.二分部分割矩阵算法特殊子阵：1阶子阵：2阶子阵：等等，最后得出所有需要考虑的全体子阵，根据并交运算，得到最后的部分割，进而得到最小割，也即最大流。

435.总结本文创新点：本文的创新点：克服了Dinic算法的占路问题障碍优化了2F算法和Greedy算法二分部分割算法大大减少了计算量445.总结未来发展方向进一步降低算法的时间复杂度进一步减少割集矩阵方程数量拓展最大流技术的实际应用45研究生期间撰写的论文[1]毛华,毛晓亮,李斌.网络最大流部分割矩阵算法.计算机科学,2011,38(12)229-233.(中文核心期刊)[2]毛华,赵小娜,毛晓亮.危险品运输中的最小风险最大流算法.计算机工程,2012,32(3),17-22.(计算机中文核心期刊)[3]毛华，赵小娜，史田敏，毛晓亮等.多部图的最大匹配算法.郑州大学学报（理学版）,2013,3,45(1)27-29.（中文核心期刊）46致谢