图算法之：最大流
这两天重点看了3个算法，最大流，匈牙利和KM。在学习的过程中颇费周折。因为我的目的是理解算法的流程，而各个网页给出的介绍要么是表述不清，要么是符号混乱。当然也可能我理解能力有限，总之觉得费劲。现在基本搞懂了流程，希望记录下来，能让广大童鞋少走些弯路。希望我能表达清楚算法的思路，咳咳~。现在介绍最大流：
问题描述：图如下，图中括号内的数字表示了沿边的实际流量记作f，括号外数字表示这条边的最大流量，称为容量记作c。图中除了起点和终点的每一点的输入量（括号里的数）之和必须等于输出量之和。起点的输出量等于终点的输入量，设之为M，则整个流的流量即为M。现在的问题是，每条边容量和实际流量已知的情况下，怎么样使整个流的流量最大。
http://dl.iteye.com/upload/attachment/495695/93b69c50-cddb-3270-bbbb-386bc08ee185.gif
解：首先引入增广链（增广路径）的概念：任意一条从起点到终点的有向路径都是由一段段正向的边或逆向的边组成的，对于一条路径来说，如果所有正向的边，都有实际流量f小于最大流量c；对于所有逆向的边，都有f>0，则这条路径是一条增广路径。
最大流和增广路径关系十分紧密。因为定理：在图G中，流是最大流的充要条件是G中不存在关于此流的增广路径。（证明略）
所以得到最大流的思路就是：逐步消灭一切增广路径。
利用Ford , Fulkerson（标号法）求图的最大流算法可分为 标号过程 和 调整过程的循环，下边给出详细步骤：
1、标号过程
在这个过程中，网络中的点分为两部分：已标号的点和未标号的点。其中已标号的点又分为：已检查的点和未检查的点。每个标号点的标号包含3部分：第一个部分表明它的前驱点，以便找出增广链；第二个部分是为确定增广链的调整量θ用的；第三部分标志其是否已被检查。
首先给起点vs标上(0,+∞)，这时vs是标号而未检查的点，其余都是未标号点，一般地，取一个标号而未检查的点vi，对一切未标号点vj：
(1) 在vi->vj边上，若fij<cij(实际流量小于最大流量)，则给vj标号(vi+,l(vj),unchecked),其中l(vj)=min(l(vi),cij-fij)。
(2) 若vj->vi边fji>0 ，给vj标号(vi-,l(vj),unchecked),其中l(vj)=min(l(vi),fji)。
vi成为标号而已检查过的点，重复上述步骤，一旦终点被标上号，表明得到一条从起点到终点的增广链，转入调整过程。
若所有标号都是已检查过，而标号过程进行不下去时，则算法结束，这时的流就是最大流。
2 调整过程
现在已经得到了标记好的各个点，首先用从终点开始（因为每一个点的标号都记录了它的上一个节点）利用回溯法找到任意一条增广路径u。令调整量θ是l(终点)(因为每一个被标记的点l(vi)的值都已经算好了，终点的l值确定能保证增广路径上的每条边都加上θ而不会超过最大流量)，对于增广路径上的正向边，其实际流f都加上θ；对于增广路径上的逆向边，其实际流f都减去θ。此时去掉所有标号，重新进入标号过程。
附加说明：此算法运行过程中会让一些边逐步的f=c，导致这些边“作废”而无法参与增广路径。最终找不到增广路径时算法结束，此时废掉的边会将图分成两部分，即：如果去掉这些废边，起点和终点将不再联通。
如有疑问，请看详细解答：
http://course.cug.edu.cn/cugFirst/operational_research/main/charpter7/p4.htm
有时间再写一写匈牙利算法和KM算法，以及3个算法的实例代码。
页:
[1]