算法最大流精.ppt

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