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

《《毛毛毕业论文答辩》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

4、是，当网络的最大弧容量为无理数时，最大流不收敛。因此，2F标号算法是伪多项式算法。62.本文算法改进的基础第二，1970年到1973年，Dinic增量网络算法的提出，使得最大流算法的复杂度进一步降低，由原来的O(nm2)和O(n2m)降低到O(m2logU)和O(nmlogU),其中U为整型网络的最大弧容量。此后很长一段时间，算法时间复杂度核心因子一直停留在O(nm)，没有能被突破。73.本文的算法内容最大流算法研究的两个出发点：(1)从增广路径出发(2)从网络的割集出发本文提出的两个算法：(1)基于枢纽度(

5、流枢纽度)的增广路算法；(2)二分部分割矩阵算法；83.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点

6、，则网络最大流已找到；93.1Dinic增量网络算法分析2.Dinic算法存在的问题：103.1Dinic增量网络算法的分析2.Dinic算法存在的问题：增广路选择的顺序不同会导致最大流的流值无法达到最优113.1Dinic增量网络算法的分析2.Dinic算法存在的问题：增广路选择的顺序不同会导致最大流的流值无法达到最优123.1Dinic增量网络算法的分析2.Dinic算法存在的问题：增广路选择的顺序不同会导致最大流的流值无法达到最优133.1Dinic增量网络算法的分析2.Dinic算法存在的问题：增广路

7、选择的顺序不同会导致最大流的流值无法达到最优143.1Dinic增量网络算法的分析2.Dinic算法存在的问题：增广路选择的顺序不同会导致最大流的流值无法达到最优153.1Dinic增量网络算法的分析2.Dinic算法存在的问题：增广路选择的顺序不同会导致最大流的流值无法达到最优163.1Dinic增量网络算法的分析2.Dinic算法存在的问题：删去已经饱和的弧，更新网络：173.1Dinic增量网络算法的分析2.Dinic算法存在的问题：此时网络的最大流的流值为：2+2=4，而实际网络的最大流为：2+2+2

8、=6；183.2基于枢纽度的增广路算法1.算法改进中的一些重要概念枢纽度：设网络N=(V,x,y,A,C)，任意uV,TV，T={v

9、其中v为u的邻点}，为了表示v点对于u点的重要程度，我们称v点的度（出度与入度之和）d(v)的倒数1/d(v)为网络的枢纽度，记为Key(v)，将枢纽度最大的点称为枢纽点。注1(1)枢纽度表示的是此点在网络连通性中的重要程度，换言之，删去此点对网络的连通性影响较大