资源描述：
《网络最大流问题算法研究【开题报告】》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、毕业设计开题报告数学与应用数学网络最大流问题算法研究一、综述本课题国内外研究动态,说明选题的依据和意义最大流问题是指在一定的条件下,要求流过网络的物流、能量流、信息流等流量为最大的问题.最大流问题已有50多年的研究历史,这段时期内,人们建立了最大流问题较为完善的理论,同时开发了大量优秀的算法.如Ford和Fulkerson增截轨算法、Dinic阻塞流算法、Goldberg推进和重标号算法以及Goldberg和Rao的二分长度阻塞流算法等等,这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用.近年来,随着计算机科学技术和网络的快速发展,网络最大流
2、问题得到了更深入的研究,并极大地推动了最大流问题的研究进展.然而,研究工作仍未结束:首先,在理论算法研究方面,人们还没有发现最大流问题算法时间复杂度的精确下界,更没有任何一个通用算法达到或接近问题的下界;其次,在算法的实际性能方面,目前算法的实际性能也不能满足许多应用问题的要求;同时,最大流问题作为特殊的线性规划问题,它远比一般线性规划问题容易解决,发现应用领域中的问题和最大流问题的联系可以使应用问题更好地得到解决.因此,关于网络最大流问题的研究具有十分重要的理论意义和实用价值.最早的算法是Dantzig提出的网络单纯刑法和Ford和Fulkerson的增载轨算
3、法,他们都是伪多项式时间算法,分别由Dinic,Edmonds和Karp等提出.1973年Dinic首次获得了时间复杂度的核心因子为算法.以后的几十年中,最大流算法获得了很大的进展.在最大流问题中,时间界是一个自然的障碍.如果我们把一个流沿从源到汇的各个路径进行分解,根据流分解定理,这些包含流的路径的总长度为.因此,对每次利用一条曾接轨的算法,时间是这类算法的下界.尽管这个下界对使用动态树数据结构或基于预流概念的算法是不适用的,但在很长一段时间内,的时间界没有被突破.时间被称为最大流问题的流分解障碍.下面看看各种算法的进展:分类算法:假设网络中已经有了一定的流,
4、考虑网络的一条边,一方面,如果该边的流还没有达到该边的容量,则我们可以继续增加该边上的流;另一方面,我们也可以减少该流,这相当于在网络中沿该流相反的方向增加流.我们称由剩余容量不为零的边和与现有流方向的相反方向的边构成的网络为剩余网络.组合方法是不断地在剩余网络中增加流量直到找到最大流.组合算法一直是最大流算法研究的主流,随着各种组合技术的发展和应用,算法的时间复杂度不断进步.目前具有最好的实际性能的算法也是组合算法,它们是增载轨类算法中的Dinic阻塞流算法和预流推进类算法的Goldberg和Tarjan推进-重标号算法.增载轨算法:沿剩余网络中从源到汇的有向
5、路径推进流.增载轨算法包括Ford和Fulkerson的标号算法、Dinic的阻塞流算法、Ahuja和Orlin的最短增载轨算法等.1956年,Ford和Fulkerson首次发现增载轨算法.由于Ford和Fulkerson算法是在剩余网络中任意选择从源到汇的有向路径作为增载轨的,增载轨的数量可能很多,最坏情况为.因此,Ford和Fulkerson算法的时间复杂度为,它是伪多项式时间的.通过两种好的选择策略可以限制增载轨的数量.意识每次都选择容量最大的增载轨,可以把增载轨的数量降为.但寻找容量最大的增载轨花的代价较大.另一种策略是每次选择长度最短的增载轨,使用这
6、种策略可以使增载轨的数量限制在,Edmonds和Karp的最短增载轨算法利用宽度优先搜索在剩余网络中寻找最短增截轨,该算法的时间复杂度为.预流推进算法:沿剩余网络中的边推进流.预流推进算法包括Karzanov的阻塞流算法、Goldberg和Tarjan的推进-重标号算法、Goldberg和Rao的二分长度阻塞流算法等,以及它们的各种启发式实现策略.和增载轨算法的思路不同,预流推进算法在剩余网络中是沿边推进尽可能多的流,直到不能向前继续推进,再把驻留在中间结点的流退回到源.1974年,Karzanov首次把无环图中阻塞流看做一个单独的问题,并建立了预流的概念来解决
7、它.Karzanov的阻塞流算法的时间复杂度为.Cherkassky把这个时间复杂度改进为.Goldberg和Tarjan利用动态树实现了这种基于预流推进的阻塞流算法,其时间复杂度为.1988年,Goldberg和Tarjan建立了距离标号的概念,并提出了推进-重标号的算法,一般推进-重标号算法的时间复杂度为,采用先进先出的实现策略和选择最高标号的策略,算法的时间复杂度分别为和.距离标号:剩余网络中每个结点的距离标号代表了该结点到汇的距离.Goldberg和Tarjan的推进-重标号算法和Ahuja与Orlin的最短增载轨算法等采用的是距离标号.复杂数据结构:为
8、了保留每次流推进的信息,
