最大网络流最小费用流模型.ppt
《最大网络流最小费用流模型.ppt》由会员分享,可在线阅读,更多相关《最大网络流最小费用流模型.ppt(24页珍藏版)》请在三一文库上搜索。
1、1,最大网络流,1 基本概念和术语 (1) 网络 G是一个简单有向图,G=(V,E),V=1,2,n。 在V中指定一个顶点s,称为源, 另一个顶点t,称为汇。 有向图G的每一条边(v,w)E,对应有一个值cap(v,w)0,称为边的容量。 这样的有向图G称作一个网络。 (2) 网络流 网络上的流是定义在网络的边集合E上的一个非负函数flow=flow(v,w),并称flow(v,w)为边(v,w)上的流量。,2,(3) 可行流 满足下述条件的流flow称为可行流: (3.1)容量约束:对每一条边(v,w)E,0flow(v,w)cap(v,w)。 (3.2)平衡约束: 对于中间顶点:流出量=流
2、入量。 即对每个vV(vs,t)有:顶点v的流出量顶点v的流入量=0,即 对于源s:s的流出量s的流入量=源的净输出量f,即 对于汇t:t的流入量t的流出量的=汇的净输入量f,即 式中f 称为这个可行流的流量,即源的净输出量(或汇的净输入量)。 可行流总是存在的。 例如,让所有边的流量flow(v,w)=0,就得到一个其流量f=0的可行流(称为0流)。,3,(4) 边流 对于网络G的一个给定的可行流flow,将网络中满足flow(v,w)=cap(v,w)的边称为饱和边;flow(v,w)0的边称为非零流边。当边(v,w)既不是一条零流边也不是一条饱和边时,称为弱流边。 (5) 最大流 最大流
3、问题即求网络G的一个可行流flow,使其流量f达到最大。即flow满足: 0flow(v,w)cap(v,w),(v,w)E;且 (6) 流的费用 在实际应用中,与网络流有关的问题,不仅涉及流量,而且还有费用的因素。此时网络的每一条边(v,w)除了给定容量cap(v,w)外,还定义了一个单位流量费用cost(v,w)。对于网络中一个给定的流flow,其费用定义为:,4,(7) 残流网络 对于给定的一个流网络G及其上的一个流flow,网络G关于流flow的残流网络G*与G有相同的顶点集V,而网络G中的每一条边对应于G*中的1条边或2条边。 设(v,w)是G的一条边。 当flow(v,w)0时,(
4、w,v)是G*中的一条边,该边的容量为cap*(w,v)=flow(v,w); 当flow(v,w)cap(v,w)时,(v,w)是G*中的一条边,该边的容量为 cap*(v,w)=cap(v,w)-flow(v,w)。 按照残流网络的定义,当原网络G中的边(v,w)是一条零流边时,残流网络G*中有唯一的一条边(v,w)与之对应,且该边的容量为cap(v,w)。 当原网络G中的边(v,w)是一条饱和边时,残流网络G*中有唯一的一条边(w,v)与之对应,且该边的容量为cap(v,w)。 当原网络G中的边(v,w)是一条弱流边时,残流网络G*中有2条边(v,w)和(w,v)与之对应,这2条边的容量
5、分别为cap(v,w) -flow(v,w)和flow(v,w)。 残流网络是设计与网络流有关算法的重要工具。,5,增广路算法,1 算法基本思想 设P是网络G中联结源s和汇t的一条路。定义路的方向是从s到t。 将路P上的边分成2类: 一类边的方向与路的方向一致,称为向前边。向前边的全体记为P+。 另一类边的方向与路的方向相反,称为向后边。向后边的全体记为P-。 设flow是一个可行流,P是从s到t的一条路,若P满足下列条件: (1)在P的所有向前边(v,w)上,flow(v,w)0,即P-中的每一条边都是非零流边。 则称P为关于可行流flow的一条可增广路。 可增广路是残流网络中一条容量大于0
6、的路。 将具有上述特征的路P称为可增广路是因为可以通过修正路P上所有边流量flow(v,w)将当前可行流改进成一个流值更大的可行流。,6,增流的具体做法是: (1)不属于可增广路P的边(v,w)上的流量保持不变; (2)可增广路P上的所有边(v,w)上的流量按下述规则变化: 在向前边(v,w)上,flow(v,w)+d; 在向后边(v,w)上,flow(v,w)-d。 按下面的公式修改当前的流。 其中d称为可增广量,可按下述原则确定:d取得尽量大,又要使变化后的流仍为可行流。 按照这个原则,d既不能超过每条向前边(v,w)的cap(v,w)-flow(v,w),也不能超过每条向后边(v,w)的
7、flow(v,w)。 因此d应该等于向前边上的cap(v,w)-flow(v,w)与向后边上的flow(v,w)的最小值。也就是残流网络中P的最大容量。 增广路定理:设flow是网络G的一个可行流,如果不存在从s到t关于flow的可增广路P,则flow是G的一个最大流。,7,2 算法描述 最大流的增广路算法如下。该算法也常称作Ford Fulkerson算法。,template class MAXFLOW const Graph ,8,3 算法的计算复杂性 增广路算法的效率由下面2个因素所确定。 (1)整个算法找增广路的次数; (2)每次找增广路所需的时间。 给定的网络中有n个顶点和m条边,且
8、每条边的容量不超过M。 可以证明,在一般情况下,增广路算法中找增广路的次数不超过nM次。 最短增广路算法在最坏情况下找增广路的次数不超过nm/2次。 找1次增广路最多需要O(m)计算时间。 因此,在最坏情况下最短增广路算法所需的计算时间为O(nm2) 。 当给定的网络是稀疏网络,即m=O(n)时,最短增广路算法所需的计算时间为O(n3)。 最大容量增广路算法在最坏情况下找增广路的次数不超过2mlogM次。 由于使用堆来存储优先队列,找1次增广路最多需要O(nlogn)计算时间。 因此,在最坏情况下最大容量增广路算法所需的计算时间为 当给定的网络是稀疏网络时,最大容量增广路算法所需的计算时间为,
9、9,预流推进算法,1 算法基本思想 增广路算法的特点是找到增广路后,立即沿增广路对网络流进行增广。 每一次增广可能需要对最多n-1条边进行操作。 最坏情况下,每一次增广需要O(n)计算时间。 有些情况下,这个代价是很高的。下面是一个极端的例子。,10,无论用哪种增广路算法,都会找到10条增广路,每条路长为10,容量为1。 共需要10次增广,每次增广需要对10条边进行操作,每条边增广1个单位流量。 10条增广路中的前9个顶点(前8条边)是完全一样的。 如果直接将前8条边的流量增广10个单位,而只对后面长为2的不同的有向路单独操作,就可以节省许多计算时间。 这就是预流推进(preflow push
10、 )算法的基本思想。 预流推进算法注重对每一条边的增流,而不必每次一定对一条增广路增流。 通常将沿一条边增流的运算称为一次推进(push)。 在算法的推进过程中,网络流满足容量约束,但一般不满足流量平衡约束。 从每个顶点(除s和t外)流出的流量之和总是小于等于流入该顶点的流量之和。 这种流称为预流(preflow)。这也是这类算法被称为预流推进算法的原因。 下面先给出预流的严格定义。 给定网络G=(V,E)一个预流是定义在G的边集E上的一个正边流函数。 该函数满足容量约束,即对G的每一条边(v,w)E,满足0flow(v,w)cap(v,w)。,11,G的每一中间顶点满足流出量小于或等于流入量
11、。 即对每个vV(vs,t)有 满足条件 的中间顶点v称为活顶点。 量 称为顶点v的存流。 按此定义,源s和汇t不可能成为活顶点。 对网络G上的一个预流,如果存在活顶点,则说明该预流不是可行流。 预流推进算法就是要选择活顶点,并通过把一定的流量推进到它的邻点,尽可能地将当前活顶点处正的存流减少为0,直至网络中不再有活顶点,从而使预流成为可行流。 如果当前活顶点有多个邻点,那么首先推进到哪个邻点呢? 由于算法最后的目的是尽可能将流推进到汇点t,因此算法应寻求把流量推进到它的邻点中距顶点t最近的顶点。 预流推进算法中用到一个高度函数h来确定推流边。 对于给定网络G=(V,E)的一个流,其高度函数h
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最大 网络 最小 费用 模型
链接地址:https://www.31doc.com/p-2737954.html