《毛毛毕业论文答辩》PPT课件.ppt

《《毛毛毕业论文答辩》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《毛毛毕业论文答辩》PPT课件.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、河北大学2013届硕士毕业论文答辩网络最大流算法研究指导教师：毛指导教师：毛 华华答辩人：答辩人：毛晓亮毛晓亮学科专业：基础数学学科专业：基础数学授予单位：河北大学授予单位：河北大学答辩日期：答辩日期：2013年年5月月1目录本文目录网络最大流研究背景算法改进的基础主要算法内容总结2研究背景 网络最大流理论的研究至今已经有将近60年的历史，最早是Dantzig(1951)从运筹学的角度出发的网络单纯形法，随着Ford和Fulkerson（1956）标号算法的提出，由图论出发的网络流理论才被系统的建立起来。50多年来，以2F标号算法为基础，大量新颖有效的算法陆续被提出，不断丰富和完善着网络流理论

2、，近年来，随着计算机技术的迅猛发展，最大流算法复杂度的下界不断被改进，同时，理论算法的实际实现效率不断提高，进而使网络最大流理论在信息传输，路网交通，物资调运，配送，图像处理等领域的应用越来越广泛，应用价值也越来越高。3研究背景尽管如此，网络最大流理论的研究还远远没有结束，许多问题亟待解决。第一，目前网络最大流算法时间复杂度的精确下界还没有被找到，更没有哪一种通用的算法达到或接近本问题的下界；第二，大量优秀算法被提出的同时，其实际实现问题也随之出现，许多算法的算法复杂度有所降低，但是实现起来却很困难，对CPU的运算速度，及内存的要求都非常高，有待进一步解决；4研究背景第三，基于图论基础上的网络

3、最大流理论，较之组合数学，运筹学上的方法，有其独有的优势，现行算法比一般的线性规划处理方法要简单很多。正是因为其简便性，因此，对于如何发现网络最大流理论的更多有价值的实际应用，本身就是一个很值得研究的重要课题。52.本文算法改进的基础 第一，1956年由Ford和Fulkerson提出的2F标号算法，此算法又被称为增广路算法，即在剩余网络中不断寻找增广路，每找到一条增广路就进行一次增流，直至找到全部增广路为止。但是，对于复杂网络，增广路寻找本身就是一个极为棘手的问题，更为无奈的是，当网络的最大弧容量为无理数时，最大流不收敛。因此，2F标号算法是伪多项式算法。62.本文算法改进的基础第二，197

4、0年到1973年，Dinic增量网络算法的提出，使得最大流算法的复杂度进一步降低，由原来的O(nm2)和O(n2m)降低到O(m2logU)和O(nmlogU),其中U为整型网络的最大弧容量。此后很长一段时间，算法时间复杂度核心因子一直停留在O(nm)，没有能被突破。73.本文的算法内容最大流算法研究的两个出发点：(1)从增广路径出发(2)从网络的割集出发本文提出的两个算法：(1)基于枢纽度(流枢纽度)的增广路算法；(2)二分部分割矩阵算法；83.1Dinic增量网络算法的分析1.算法的基本步骤：Step0:初始化网络的可行流f0；Step1:构造网络的增量网络N(f)；Step2:对增量网络

5、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算法存在的问题：增广路选择的顺序不

6、同会导致最大流的流值无法达到最优增广路选择的顺序不同会导致最大流的流值无法达到最优123.1Dinic增量网络算法的分析2.Dinic算法存在的问题：增广路选择的顺序不同会导致最大流的流值无法达到最优增广路选择的顺序不同会导致最大流的流值无法达到最优133.1Dinic增量网络算法的分析2.Dinic算法存在的问题：增广路选择的顺序不同会导致最大流的流值无法达到最优增广路选择的顺序不同会导致最大流的流值无法达到最优143.1Dinic增量网络算法的分析2.Dinic算法存在的问题：增广路选择的顺序不同会导致最大流的流值无法达到最优增广路选择的顺序不同会导致最大流的流值无法达到最优153.1Di

7、nic增量网络算法的分析2.Dinic算法存在的问题：增广路选择的顺序不同会导致最大流的流值无法达到最优增广路选择的顺序不同会导致最大流的流值无法达到最优163.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点的度（出度与入度之和

8、）d(v)的倒数1/d(v)为网络的枢纽度，记为Key(v)，将枢纽度最大的点称为枢纽点。注1(1)枢纽度表示的是此点在网络连通性中的重要程度，换言之，删去此点对网络的连通性影响较大。193.2基于枢纽度的增广路算法(2)枢纽度是一个相对的概念，考察的对象为与已知点相邻的点集中的点。(3)对于一个给定的网络N=(V,x,y,A,C)，我们规定Key(x)=Key(y)=1，即，总是认为网络的发点和收点是枢纽点，其现实意义也是显而易见的。枢纽路：设网络N=(V,x,y,A,C)，对N中任一条f可增路P，若P上所有的点均为枢纽点，则称P为网络N的一条枢纽路。203.2基于枢纽度的增广路算法产出比值

9、设网络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.Begin Val=0;S=x;while N中存在增广路P;do while(v!=y)Key(v)=为u的邻点,uS;令 Val +=223.2基

10、于枢纽度的增广路算法更新增量网络；End仍然以原来的网络的为例：233.2基于枢纽度的增广路算法首先，以零流为可行流，即Val =0，对源点x的邻点进行标号，考虑到Key(u)=1/3,Key(v)=1/2，Key(w)=1/3，因而选择v点作为枢纽路上的一点，v点的邻点仅有c点，因此，下一个枢纽点为c，同理，对y进行标号，于是第一条枢纽路形成，即P1=xvcy 243.2基于枢纽度的增广路算法同理，第二条枢纽路：253.2基于枢纽度的增广路算法第三条枢纽路：第三条枢纽路：263.2基于枢纽度的增广路算法这样，整个网络的最大流为：这样，整个网络的最大流为：2+2+2=6，更新网络之后，网，更新

11、网络之后，网络中已经没有枢纽路络中已经没有枢纽路273.3基于流枢纽度的增广路算法 上节算法基于枢纽度考虑，优先考虑网络的连通性，对于流上节算法基于枢纽度考虑，优先考虑网络的连通性，对于流量的要求没有做限制，这一节将流量的限制加入到算法中，进一量的要求没有做限制，这一节将流量的限制加入到算法中，进一步优化上述算法，使得网络最大流的求解过程更具目标性，增广步优化上述算法，使得网络最大流的求解过程更具目标性，增广路的选择更具顺序性。为了研究的方便，本节仍然以可分层网络路的选择更具顺序性。为了研究的方便，本节仍然以可分层网络为例，在分好层的基础上，以深度优先原则进行枢纽路的寻找，为例，在分好层的基础

12、上，以深度优先原则进行枢纽路的寻找，进而得到网络的最大流。进而得到网络的最大流。283.3基于流枢纽度的增广路算法Input:网络N=(V,x,y,A,C).Output:网络N的一个最大流Val.BeginVal=0;S=x;while N中存在增广路P;do while(v!=y)Impo(v)=max Impo(vi),vi为u的邻点,uS;Val +=293.3基于流枢纽度的增广路算法End网络实例运行结果与理论值十分吻合网络实例运行结果与理论值十分吻合303.3基于流枢纽度的增广路算法例3如图所示网络N=(V,x,y,A,C)：利用流枢纽度增广路算法来求解网络的最大流。313.3基于

13、流枢纽度的增广路算法首先，初始化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基于流枢纽度的增广路算法max Impo(v1)=5/28，max Impo(v3)=8/27，显然，max Impo(v3)max Impo(v1)，由算法的执行过程可知，枢纽路上选择v3点，且指向v4点，依照深度优先的原则，下一个点将会标到v

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

15、C),则，N与N-1的最大流值相等。(2)(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阶子阵：等等，最后得出所有需要考虑 的全体子阵，根据并交运算

16、，得到最后的部分割，进而得到最小割，也即最大流。435.总结 本文创新点：本文的创新点本文的创新点：克服了克服了Dinic算法的占路问题障碍算法的占路问题障碍优化了优化了2F算法和算法和Greedy算法算法二分部分割算法大大减少了计算量二分部分割算法大大减少了计算量445.总结未来发展方向未来发展方向进一步降低算法的时间复杂度进一步降低算法的时间复杂度进一步减少割集矩阵方程数量进一步减少割集矩阵方程数量拓展最大流技术的实际应用拓展最大流技术的实际应用45研究生期间撰写的论文1 毛华毛华,毛晓亮毛晓亮,李斌李斌.网络最大流部分割矩阵算法网络最大流部分割矩阵算法.计算计算机机科学科学,2011,3

17、8(12)229-233.(中文核心期刊中文核心期刊)2 毛华毛华,赵小娜赵小娜,毛晓亮毛晓亮.危险品运输中的最小风险最大流算法危险品运输中的最小风险最大流算法.计算机工程计算机工程,2012,32(3),17-22.(计算机中文核心期刊计算机中文核心期刊)3毛华，赵小娜，史田敏，毛晓亮等毛华，赵小娜，史田敏，毛晓亮等.多部图的最大匹配算法多部图的最大匹配算法.郑州大学学报（理学版）郑州大学学报（理学版）,2013,3,45(1)27-29.（中文核心期刊）（中文核心期刊）46致谢 首先首先,我要向我的导师毛华教授表示最诚挚的谢意我要向我的导师毛华教授表示最诚挚的谢意.毛老师踏实严格的求知精神

18、和严谨细致的研究工作作毛老师踏实严格的求知精神和严谨细致的研究工作作风是我终生学习的楷模风是我终生学习的楷模.在我攻读硕士研究生学位期在我攻读硕士研究生学位期间间,毛老师在学习上严格要求毛老师在学习上严格要求,使我得到了很好的锻炼使我得到了很好的锻炼.在此在此,我对毛老师给予我的无微不至的关怀和教导表我对毛老师给予我的无微不至的关怀和教导表示衷心的感谢示衷心的感谢!我也感谢一直以来支持和帮助过我的同学和老师，我也感谢一直以来支持和帮助过我的同学和老师，是他们让我在研究生期间获益匪浅。是他们让我在研究生期间获益匪浅。感谢对论文评审并提出宝贵意见的各位专家感谢对论文评审并提出宝贵意见的各位专家!47感谢各位评审老师的耐心指导！48