算法最大流.ppt

算法最大流
第1页，本讲稿共21页
本节目标
了解什么是最大流问题，及相关基本概念
了解求最大流的增广路算法及预流推进算法
学会对问题建模，及相关转化方法
第2页，本讲稿共21页
最大网络流
网络
简单有向图，有源，后边(v,w)上，flow(v,w)-d。
其中d称为可增广量，可按下述原则确定：d取得尽量大，又要使变化后的流仍为可行流。
第10页，本讲稿共21页
增广路算法
d的选取
d既不能超过每条向前边(v,w)的cap(v,w)-flow(v,w)，也不能超过每条向后边(v,w)的flow(v,w)。
因此d应该等于向前边上的cap(v,w)-flow(v,w)与向后边上的flow(v,w)的最小值。也就是残流网络中P的最大容量。
增广路定理：设flow是网络G的一个可行流，如果不存在从s到t关于flow的可增广路P，则flow是G的一个最大流。
关键-寻找可增广路
第11页，本讲稿共21页
预流推进算法
增广路算法的特点是找到增广路后，立即沿增广路对网络流进行增广。
每一次增广可能需要对最多n-1条边进行操作。
最坏情况下，每一次增广需要O(n)计算时间。
有些情况下，这个代价是很高的。下面是一个极端的例子。
第12页，本讲稿共21页
基本思想
预流推进算法注重对每一条边的增流，而不必每次一定对一条增广路增流。通常将沿一条边增流的运算称为一次推进（push）。
给定网络G=(V,E)一个预流是定义在G的边集E上的一个正边流函数。在算法的推进过程中，网络流满足容量约束，但一般不满足流量平衡约束。
从每个顶点（除s和t外）流出的流量之和总是小于等于流入该顶点的流量之和。
第13页，本讲稿共21页
满足流入流量>流出流量的中间节点称为活节点，其中没有流出的流量称为存流
对网络G上的一个预流，如果存在活顶点，则说明该预流不是可行流。
预流推进算法就是要选择活顶点，并通过把一定的流量推进到它的邻点，尽可能地将当前活顶点处正的存流减少为0，直至网络中不再有活顶点，从而使预流成为可行流。
第14页，本讲稿共21页
高度函数h
用来确定推流边。
对于给定网络G=(V,E)的一个流，其高度函数h是定义在G的顶点集V上的一个非负函数。该函数满足：
对于G的残流网络中的每一条边(u,v)有，h(u)  h(v)+1；
h(t)=0。
G的残流网络中满足h(u) = h(v)+1的边(u,v)称为G的可推流边。
第15页，本讲稿共21页
一般的预流推进算法
步骤0：构造初始预流flow：
对源顶点s的每条出边(s,v)令flow(s,v)=cap(s,v)；对其余边(u,v)令flow(u,v)=0。构造一有效的高度函数h。
步骤1：如果残量网络中不存在活顶点，则计算结束，已经得到最大流；否则转步骤2。
步骤2：在网络中选取活顶点v。
如果存在顶点v的出边为可推流边，则选取一条这样的可推流边，并沿此边推流。
否则令h(v) = min{h(w)+1 | (v,w)是当前残流网络中的边}，并转步骤1。
第16页，本讲稿共21页
一般的预流推进算法的每次迭代是一次推进运算或者一次高度重新标号运算。
如果推进的流量等于推流边上的残留容量，则称为饱和推进，否则称为非饱和推进。
算法终止时，网络中不含有活顶点。此时只有顶点s和t的存流非零。此时的预流实际上已经是一个可行流。
算法在计算过程中可以保证网络中不存在增广路。根据增广路定理，算法终止时的可行流是一个最大流。
关键：一般的预流推进算法并未给出如何选择活顶点和可推流边。不同的选择策略导致不同的预流推进算法。
第17页，本讲稿共21页
小结
增广路算法-通过寻找可增广路并沿路增加流量来求出最大值。
预流推进算法-一开始就从源点全部流出，逐步推进，实在无法推进的退回以达到最大值。
第18页，本讲稿共21页
最大流问题的变换
多源点多汇点的最大流问题
可行流问题
有顶点约束的最大流问题
二分图的最大匹配问题
变换成线性规划问题
第19页，本讲稿共21页
小结
最小费用最大流问题
网络流问题是一个比较复杂也非常实用的问题，有多种不同变种和解决方法，感兴趣的同学可以自行阅读相关文献
时间复杂度
正确性证明
具体实现
只要求：算法了解/建模/转化
第20页，本讲稿共21页
练习
8-10，8-15
现在BNU决定为N名大一新生重新安排宿舍，一共有M间个性化宿舍可供选择，每间宿舍的位置、窗户大小、墙纸颜色、房间布置以及住宿费都各不相同，因此，学校做了一个调查，每个同学都列出他愿意住的房间，排名不分先后，用变量R[i][j]表示，R[i][j]=1表示学生i愿意住在房间j，R[i][j]=0则表示不愿意。但是每间房间容量