《《毛毛毕业论文答辩》PPT课件》由会员分享，可在线阅读，更多相关《《毛毛毕业论文答辩》PPT课件（49页珍藏版）》请在金锄头文库上搜索。
1、1,河北大学2013届硕士毕业论文答辩,网络最大流算法研究,指导教师：毛 华 答辩人： 毛晓亮 学科专业：基础数学 授予单位：河北大学 答辩日期：2013年5月,2,目录,3,研究背景,网络最大流理论的研究至今已经有将近60年的历史，最早是Dantzig(1951)从运筹学的角度出发的网络单纯形法，随着Ford和Fulkerson（1956）标号算法的提出，由图论出发的网络流理论才被系统的建立起来。50多年来，以2F标号算法为基础，大量新颖有效的算法陆续被提出，不断丰富和完善着网络流理论，近年来，随着计算机技术的迅猛发展，最大流算法复杂度的下界不断被改进，同时，理论算法的实际实现效率不断提高，
2、进而使网络最大流理论在信息传输，路网交通，物资调运，配送，图像处理等领域的应用越来越广泛，应用价值也越来越高。,4,研究背景,尽管如此，网络最大流理论的研究还远远没有结束，许多问题亟待解决。 第一，目前网络最大流算法时间复杂度的精确下界还没有被找到，更没有哪一种通用的算法达到或接近本问题的下界； 第二，大量优秀算法被提出的同时，其实际实现问题也随之出现，许多算法的算法复杂度有所降低，但是实现起来却很困难，对CPU的运算速度，及内存的要求都非常高，有待进一步解决；,5,研究背景,第三，基于图论基础上的网络最大流理论，较之组合数学，运筹学上的方法，有其独有的优势，现行算法比一般的线性规划处理方法要
3、简单很多。正是因为其简便性，因此，对于如何发现网络最大流理论的更多有价值的实际应用，本身就是一个很值得研究的重要课题。,6,2.本文算法改进的基础,第一，1956年由Ford和Fulkerson提出的2F标号算法，此算法又被称为增广路算法，即在剩余网络中不断寻找增广路，每找到一条增广路就进行一次增流，直至找到全部增广路为止。但是，对于复杂网络，增广路寻找本身就是一个极为棘手的问题，更为无奈的是，当网络的最大弧容量为无理数时，最大流不收敛。因此，2F标号算法是伪多项式算法。,7,2.本文算法改进的基础,第二，1970年到1973年，Dinic增量网络算法的提出，使得最大流算法的复杂度进一步降低，
4、由原来的O(nm2)和O(n2m)降低到O(m2logU)和O(nmlogU),其中U为整型网络的最大弧容量。此后很长一段时间，算法时间复杂度核心因子一直停留在O(nm)，没有能被突破。,8,3.本文的算法内容,最大流算法研究的两个出发点： (1) 从增广路径出发 (2) 从网络的割集出发 本文提出的两个算法： (1) 基于枢纽度(流枢纽度)的增广路算法； (2) 二分部分割矩阵算法；,9,3.1 Dinic增量网络算法的分析,1.算法的基本步骤： Step0:初始化网络的可行流f0； Step1:构造网络的增量网络N(f)； Step2:对增量网络N(f)分层，若分层不能达到汇点y，则网络的
5、最大流为f0，否则转下步； Step3:构造网络的辅助网络AN(f)，在AN(f)中寻找x-y有向路，即可增路； Step4:沿可增路增流完毕之后，删去已经被注满的边，反复增流，直至AN(f)中不存在x-y有向路为止； Step5:循环执行以上步骤，若网络已不能分层至y点，则网络最大流已找到；,10,3.1 Dinic增量网络算法分析,2.Dinic算法存在的问题：,11,3.1 Dinic增量网络算法的分析,2. Dinic算法存在的问题：,增广路选择的顺序不同会导致最大流的流值无法达到最优,12,3.1 Dinic增量网络算法的分析,2. Dinic算法存在的问题：,增广路选择的顺序不同会
6、导致最大流的流值无法达到最优,13,3.1 Dinic增量网络算法的分析,2. Dinic算法存在的问题：,增广路选择的顺序不同会导致最大流的流值无法达到最优,14,3.1 Dinic增量网络算法的分析,2. Dinic算法存在的问题：,增广路选择的顺序不同会导致最大流的流值无法达到最优,15,3.1 Dinic增量网络算法的分析,2. Dinic算法存在的问题：,增广路选择的顺序不同会导致最大流的流值无法达到最优,16,3.1 Dinic增量网络算法的分析,2. Dinic算法存在的问题：,增广路选择的顺序不同会导致最大流的流值无法达到最优,17,3.1 Dinic增量网络算法的分析,2.
7、Dinic算法存在的问题： 删去已经饱和的弧，更新网络：,18,3.1 Dinic增量网络算法的分析,2. Dinic算法存在的问题： 此时网络的最大流的流值为：2+2=4，而实际网络的最大流为：2+2+2=6；,19,3.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) 枢纽度表示的是此点在网络连通性中的重要程度，换言之，删去此点对网
8、络的连通性影响较大。,20,3.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的一条枢纽路。,21,3.2 基于枢纽度的增广路算法,产出比值 设网络N=(V,x,y,A,C)，任意vV, 为点v的任一出弧，为点v的任一入弧，其弧容量分别为，定义 称Tran(v)为v点的产出比值。
9、 注 (1) 由Tran(v)的定义可知，Tran(v)总是小于1的值。 (2) 给出一个新的标记，Impo(v)= Key(x) Tran(v)，称Impo(v)为v点的流枢纽度。,22,3.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 +=,23,3.2 基于枢纽度的增广路算法,更新增量网络； End 仍然以原来的网络的为例：,24,3.2 基于
10、枢纽度的增广路算法,首先，以零流为可行流，即Val =0，对源点x的邻点进行标号，考虑到Key(u)=1/3, Key(v)=1/2， Key(w)=1/3，因而选择v点作为枢纽路上的一点，v点的邻点仅有c点，因此，下一个枢纽点为c，同理，对y进行标号，于是第一条枢纽路形成，即P1=xvcy,25,3.2 基于枢纽度的增广路算法,同理，第二条枢纽路：,26,3.2 基于枢纽度的增广路算法,第三条枢纽路：,27,3.2 基于枢纽度的增广路算法,这样，整个网络的最大流为：2+2+2=6，更新网络之后，网络中已经没有枢纽路,28,3.3 基于流枢纽度的增广路算法,上节算法基于枢纽度考虑，优先考虑网络
11、的连通性，对于流量的要求没有做限制，这一节将流量的限制加入到算法中，进一步优化上述算法，使得网络最大流的求解过程更具目标性，增广路的选择更具顺序性。为了研究的方便，本节仍然以可分层网络为例，在分好层的基础上，以深度优先原则进行枢纽路的寻找，进而得到网络的最大流。,29,3.3 基于流枢纽度的增广路算法,Input: 网络N=(V,x,y,A,C). Output: 网络N的一个最大流Val. Begin Val=0;S=x; while N中存在增广路P; do while(v!=y) Impo(v)=max Impo(vi), vi为u的邻点,uS; Val +=,30,3.3 基于流枢纽度
12、的增广路算法,End,网络实例运行结果与理论值十分吻合,31,3.3 基于流枢纽度的增广路算法,例 3 如图所示网络N=(V,x,y,A,C)： 利用流枢纽度增广路算法来求解网络的最大流。,32,3.3 基于流枢纽度的增广路算法,首先，初始化Val=0，S=x,考察x的邻点v1，v3，现在分别计算其枢纽度和产出比值： Key(v1)=1/4，Tran(v1)= Key(v3)=1/3，Tran(v3)=,33,3.3 基于流枢纽度的增广路算法,因此，流枢纽度为： Impo(v1)= Key(v1) Tran(v1)= Impo(v3)= Key(v3) Tran(v3)=,34,3.3 基于流
13、枢纽度的增广路算法,max Impo(v1)=5/28，max Impo(v3)=8/27，显然，max Impo(v3) max Impo(v1)，由算法的执行过程可知，枢纽路上选择v3点，且指向v4点，依照深度优先的原则，下一个点将会标到v4，显然，第一条枢纽路为P1=xv3v4y,35,3.3 基于流枢纽度的增广路算法,同理，得到其他的流枢纽度增广路，最终得到更新后的网络：,36,4. 二分部分割矩阵算法,本节算法的思想如下： 首先，对于网络N=(V,x,y,A,C)，构造其逆向网络=( V,y,x,A-1,C)，同时构造出两者的部分割矩阵； 其次，由连通性定理，寻找N的部分割矩阵的子阵
14、，当子阵阶数较大时，转向求N-1的部分割矩阵的子阵； 最后，对子阵进行集合的并交运算，并最终求得网络的最小割，也即，网络的最大流。,37,4. 二分部分割矩阵算法,得到的几个定理： 流等价定理 设网络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的最小割。,38,4. 二分部分割矩阵算法,2. 给出的一些概念： (1)(部分割容量矩阵)下面的n-1阶容量矩阵T称为网络N的部分割容量矩阵 :,39,4. 二分部分割矩阵算法,(2)
15、部分割容量矩阵的特殊子阵 =,40,4. 二分部分割矩阵算法,网络实例：,41,4. 二分部分割矩阵算法,首先，构造网络和逆向网络的部分割容量矩阵： T=,42,4. 二分部分割矩阵算法,逆向网络：,43,4. 二分部分割矩阵算法,特殊子阵： 1阶子阵： 2阶子阵： 等等，最后得出所有需要考虑 的全体子阵，根据并交运算，得到最后的部分割，进而得到最小割，也即最大流。,44,5. 总结,本文创新点：,45,5. 总结,46,研究生期间撰写的论文,1 毛华, 毛晓亮, 李斌. 网络最大流部分割矩阵算法. 计算 机科学, 2011, 38(12) 229-233. (中文核心期刊) 2 毛华, 赵小
16、娜, 毛晓亮. 危险品运输中的最小风险最大流算法. 计算机工程, 2012, 32(3), 17-22. (计算机中文核心期刊) 3毛华，赵小娜，史田敏，毛晓亮等.多部图的最大匹配算法.郑州大学学报（理学版）,2013,3,45(1)27-29.（中文核心期刊）,47,致谢,首先,我要向我的导师毛华教授表示最诚挚的谢意.毛老师踏实严格的求知精神和严谨细致的研究工作作风是我终生学习的楷模.在我攻读硕士研究生学位期间,毛老师在学习上严格要求,使我得到了很好的锻炼.在此,我对毛老师给予我的无微不至的关怀和教导表示衷心的感谢! 我也感谢一直以来支持和帮助过我的同学和老师，是他们让我在研究生期间获益匪浅。 感谢对论文评审并提出宝贵意见的各位专家!,48,感谢各位评审老师的耐心指导！,谢谢大家,
