算法导论自学笔记(7)

终于晕晕乎乎的学完了动态规划和线性规划,这一节开始学习传说中的网络流。

在开始学习之前还是要总结一下动态规划、线性规划,因为,网络流和它们是有关系的,算是为网络流的学习铺垫一下吧。

规划论(Mathematical Programming)

规划论又称作“数学规划”,是运筹学的一个分支。之所以搞出这样一个东西,是为了更好的利用身边的资源,最好的达到最终目的。

比如找女朋友,要考虑下自身的条件,最大化发挥自己的能力并将其追到手,这就需要规划。过节抢票需要规划,北京买房需要规划,职业需要规划,人生也需要规划。总之,规划很重要。

因为重要,所以关注。就有了这么个规划论。任何问题一抽象,就成了数学问题,所以又称为“数学规划”。

回到动态规划和线性规划,就好比白猫和黑猫,都是规划的方法,核心目标就是好好利用有限的资源,达到最终的目标。

更深入的关系清华大学《运筹学》一书已经总结好了:

动态规划、线性规划和非线性规划都属于数学规划的范围,所研究的对象本质上都是一个求极值的问题,都是利用迭代法去逐步求解的。不过,线性规划和非线性规划所研究的问题,通常是与时间无关的,故又称它们为静态规划。线性规划迭代中的每一步是就问题的整体加以改善的。而动态规划所研究的问题是与时间有关的,它是研究具有多阶段决策过程的一类问题,将问题的整体按时间或空间的特征而分成若干个前后衔接的时空阶段,把多阶段决策问题表示为前后有关联的一系列单阶段决策问题,然后逐个加以解决,从而求出整个问题的最优决策序列。因此,对于某些静态的问题,也可以人为地引入时间因素,把它看作是按阶段进行的一个动态规划问题,这就使得动态规划成为求解某些线性、非线性规划的有效方法。

网络流(Network Flow)

网络流和线性规划、动态规划是有关系的。它们都属于数学规划,也就是用数学的方法来帮助决策。(详情参考清华大学《数学规划》)这样来看,就没有神秘可言了。小样,换个马甲我还认识你。所以,网络流也是一个解决极值问题的数学方法。

要解决问题,总得先有个靠谱的模型吧。动态规划和线性规划里边都有公式啥的。总之,要先形式化(建模),再解决。所以,就有了流网络。

流网络(Flow Network)

顾名思义,流网络是一种用流构成的网络,如下图。

可以把边想象成自来水的管道,把节点想象成管道的连接组件。其中,管道的容量不一定相同,所以就有了不同的边的权重(管道容量是一个大于等于0的常量)。流网络是一个有向图,所以,管道是有方向的(水的流向只能按照管道的方向流)。注意图中两个特殊的连接组件,s代表源,也就是水的入口,t代表汇,也就是水的出口。也就是说,水从s点灌入,从t点流出,具体有多少水流入s,我们不用管,反正是源源不断;从t流出的水去哪,我们也不用操心。

这样,我们就得到了一个流网络,s是流的入口,t是流的出口,s和t之间有若干个管道连接。要谨记这个流网络中管道的容量限制和方向限制,若是没有它,又何必来学网络流。

流(Flow)

流网络可以看成是一张线路图,这里是自来水管道的线路图,相当于硬件基础设施。

我们现在要做的是使用这个基础设施,也就是往管道里灌水,确保每个管道里的流量不超过容量限制。比如,我们可以这样灌,如下图。边的权重增加了流量参数,使用斜线与容量进行分隔。

注意:这里的所有图中,如果有斜线标识,则左侧表示流,右侧表示容量。如果没有斜线,则只是表示容量。

对流网络灌水得到的就是“流”。当然,这只是其中一种满足流量不超过容量限制的灌水方法。还可以有很多种灌水的方法。但是都要遵循以下两个原则:

  • 容量限制:管道的流量不能超过容量。
  • 流量守恒:流入管道连接组件的流量等于流出的流量。

至此,我们成功的得到了“流”。

s-t流(s-t Flow)

现实往往是不按套路出牌的。比如,连接的地方(节点)可能有权重,能够蓄水。比如,有多个源多个汇。比如,有多个管道连接两个节点。

总之,现实的种种迹象表明,我们需要设计一个兼容并包的模型,考虑种种情况。

但是,我们不想考虑那么多情况。

于是,就有了一个小伙想了个点子,定义一种标准模型,我们只研究这个标准的模型。其它的情况通过一些方法转化成这个标准模型。

是的,这个标准模型就是s-t流。一些转化方法如下图。

最大流(Maximum Flow)

费尽心思,从初步的流网络,到我们比较喜欢的标准形式s-t流,是时候考虑正事儿了。

流网络是固定的,但是流是不确定的。所以,我们想在多种灌水的方法中寻找最佳。

何为最佳?

在源灌入大量的水,通过选择最好的管道流量和流向,使得汇流出的流量最大。但是,最大流不是想找就能找到的,所以这是个问题,即最大流问题。

Trial 1: Dynamic programming

既然是数学规划,首先想到的是能不能使用动态规划。

现实情况是,目前还没有解决最大流问题的动态规划算法。

Trial 2: Iteration

想到的另外一种方法是迭代法,伪代码表示如下。

    x = x0;
    while true do
        x = improve(x);
        if stopping(x) then
            break
        end if
    end while
    return x

主要是思想是从某个流开始,不断的改进这个流,直到到达我们想要的最大流。

不得不说,这想法太粗略了。一些问题没有解决,比如,如何选择开始的流,如何改进,何时停止算法。

为了解决这些问题,我们需要继续补充一些基础知识。这样才能干掉这个问题。

(为什么不试试线性规划?线性规划是可以解决的,但是对于这种网络的结构,并不能很高效。)

割(Cut)

对于一个流网络,在若干个管道上切一刀,使这个网络分成两部分,这两部分将无法连通。所以,我们有很多种切割的方法,把这个网络分成两部分。每一种切割的方法对应于一个“割”。

s-t割(s-t Cut)

s-t割是一种特殊的“割”,这种切割的方式需要保证在切割之后s和t不再连通,即s和t不属于同一部分了。

对于一个s-t割,必然会把s和t分到两个小网络中,并且切坏了若干个管道。这两个小网络之间的管道容量之和就是割的值,只计算从包含s的小网络流向包含t的小网络的管道容量之和,反方向不考虑。一个s-t割如下图。

可以计算出,割的值为12+14=26。可以看到,割的值只与流网络有关,和流无关。对于一个确定的流网络,一刀切下去,割的值就确定了。

最小割(Minimum Cut)

对于一个流网络,我们可以得到多个割的值,因为切的方法有很多种,如下图。

在这里,我们更关心割值最小的情况,即最小割。为什么更关心最小割?下面会说~

净流量(Net Flow)

注意到,割的值是和流无关的,只与流网络有关。也就是说,割的值只是取决于管道的容量和方向,以及切的方法。

如果我们观察一下流,发现了一个规律,如下图。

真的是固定值有木有!这个固定值就是净流量。之所以有这个规律,是因为流量守恒。

需要注意,在计算净流量时,需要考虑两个方向的值,并求代数和。从s流向t记为正,从t流向s记为负。对于割值的计算,则无需考虑从t流向s的。因为割值实际计算的是管道容量,净流量考虑的是真实的流量。

残留网络(Residual Network)

残留网络,顾名思义,就是流网络中去掉流剩下的网络。对于某条管道,其容量减去流以后剩下的流构成的网络,就形成了残留网络。每一个流会对应一个残留网络,残留网络 = 流网络 - 流,如下图。

需要说明的是,蓝色的边称作反向边,方向与原来的方向相反,数值为原来流量的值。

为什么要加上这个看似多余的反向边?

反向边的作用就是给程序一个可以后悔的机会。(来自这里

也就是说,加这个边是为了寻找最大流的程序的执行。

增广路径(Augmenting Path)

扯这么多,主要是为了引出这个增广路径。因为增广路径能帮我们找到最大流。

增广路径就是残余网络中的一条s到t方向的路径,如下图。

如果我们找到了这样一条路径,说明原来的流不够大,还可以在这条路径上压入一些流量,在这里是3,取11、12、3中最小值。

这样,我们就可以得到更大的流。

思考

从流(我们更关心最大流),到割(我们更关心最小割),到残留网络,再到增广路径,我们在做啥子吗?

我的理解是,这些流呀割呀都是理论储备,最终是想证明一句话:残留网络$G_f$中不包含增广路径时,f就是G的最大流。

而残留网络、增广路径是解决这个最大流问题的手段,通过寻找增广路径的方法来改进当前的流,朝最大流逼近。但是,问题是何时停止算法呢?这就是理论储备部分告诉我们的,如下图。

最大流最小割定理(Max-Flow Min-Cut Theorem)

重述一遍,残留网络$G_f$中不包含增广路径时,f就是G的最大流(或者说,最大流的流量等于最小割的容量)。

这就是传说中的最大流最小割定理。

这个可以用反证法证明,假设当不包含增广路径时没有达到最大流,那么就会找到一条路径来增大流,也就找到了增广路径,所以矛盾。大致是这样证明。

Ford-Fulkerson方法

Ford-Fulkerson是一种求解最大流的方法,依赖于上面积淀的基础知识(主要是残留网络、增广路径、割的功劳),也称作“扩充路径方法”。之所以称之为方法而不是算法,是因为这个只是一种指导思想,在此指导之下,有很多种实现方式。

Ford-Fulkerson是一种迭代法,过程如下:

  1. 流网络中所有顶点对的流大小清零(此时,网络流为零)
  2. 每次迭代,通过寻找一条增广路径来增加流的值
  3. 无法找到增广路径时,迭代结束

可以看到,最关键问题是如何寻找增广路径,而Ford-Fulkerson方法的效率正取决于此。如果选择方法不好,就有可能每次增加的流非常少,而算法运行时间非常长,甚至无法终止。

但是,Ford-Fulkerson并没有告诉我们如何寻找增广路径。所以,它是个方法,而不是算法,伪代码如下。

    initialize f(e) = 0 for all e
    while there is a s-t path in residual graph Gf do
        arbitrarily choose an s-t path P in Gf
        f = augment(P, f)
    end while

    augment(P, f)
        let b = bottleneck(P)
        for each edge e = (u, v) ∈ P do
            if (u, v) is a forward edge then
                increase f(u, v) by b
            else
                decrease f(u, v) by b
            end if
        end for

其中,augment是一个改变当前流的函数,即使用找到的增广路径P来压入流,增大当前的流f。而bottleneck从当前的增广路径P中找到瓶颈边(残留网络中,路径上流量最小的边),把这个流量压入。

正是因为在选择增广路径时是arbitrarily,所以Ford-Fulkerson方法有多种实现。

Scaling technique

第一种是scaling的方法,通过伪代码更好解释。

    initialize f(e) = 0 for all e
    let △ = C
    while △ ≥ 1 do
        while there is a s-t path in Gf(△) do
            choose a s-t path
            f' = augment(P, f)
            f = f'
       end while
       △ = △ / 2

可以看到,通过定义一个△来调节增广路径的选择顺序。C是一个定义的常熟。如果残留网络中的边(流量值)小于C,则“删除”该边,在新的网络中选择增广路径。如果这样的网络中找不到增广路径(也就是说,所有的边都不符合△的限制),则把△缩放为原来的一半,继续寻找增广路径。直到△不满足大于等于1时,算法结束。

例子来自卜老师的课件,△初始化为96。第一次的时候,残留网络的所有边被“删除”(标记为蓝色),因为都小于96。然后△调整为96/2=48,这样就获得了一条增广路径,并压入流。直到找不到增广路径,算法结束,如下图。

可以看到,scaling方法是通过加一个△(阈值)来选择增广路径的。通过这个阈值,可以尽可能的一次压入多一些的流。我们的目标是迭代的次数少且每次压入的流要多。

Edmonds-Karp

Edmonds-Karp算法是使用BFS(广度优先搜索)的方式,选择最近的路径作为增广路径,伪代码如下。

    initialize f(e) = 0 for all e
    while there is a s-t path in Gf do
        choose a shortest s-t path in Gf using BFS
        f' = augment(P, f)
        f = f'
    end while

补充

走了好久终于等到现在...

总结来说,前面一直在铺垫,积累些基础知识,为了得到最大流最小割定理,然后证明Ford-Fulkerson方法能够获得最大流。

但是,这终归是个方法。方法没有告诉我们哪一种寻找增广路径的算法是最好的。于是就有人搞了各种算法,进行了各种测试,性能也就各不相同了,如下图。

总之,是为了算法实现的更好,终极目标是高效的找到最大流,也就是解决最大流问题咯。

一些参考:

  1. http://www.csie.ntnu.edu.tw/~u91029/Cut.html#2
  2. http://blog.csdn.net/leolin_/article/details/7202691
  3. http://blog.csdn.net/smartxxyx/article/details/9293665
  4. http://blog.csdn.net/kk303/article/details/6728400
  5. http://www.cnblogs.com/luweiseu/archive/2012/07/14/2591573.html
  6. http://chhaj5236.blog.163.com/blog/static/112881081200982835124243/
  7. http://xpgc.vicp.net/course/ada4ia/TechDoc/ch09/ia-09-maxflow.pdf

-- EOF --