论文部分内容阅读
在高速公路网中有车流，在互联网上有信息流，在自来水管网中有水流，在公用电网中有电流，等等。但凡网络，大都和某种流联系在一起;网络的作用，就是要保障那些流的畅通。对网络中流的研究是具有普遍意义的主题。
研究网络中的流问题可有多个不同的视角和目标追求。本文讨论两个节点之间可能经过的最大流量。我们从简单例子开始，建立讨论这个话题的语境。
图1所示为一个3节点{s，a，t}的有向网络，边上的数字表示能支持的流量（不妨看成是单位时间能通过的车辆数），一般也称为对应边的“容量”。这个例子数据表明s—a边的容量为3，a—t边的容量为2。想象为道路，也就相当于是说s—a路段要比a—t路段宽一些。边的箭头方向则表示“单行线”的方向。
现在的问题是，如果我们要不断从s发出开往t的车，单位时间能发多少辆？几乎不用多想，你马上会认识到3是不行的，最多是2。而且如果有人说1，你则会说每条边的容量都还有剩余，因而流量还可以增加。于是我们说，2就是这个网络中从s到t的最大流量。并且，如果面对的不止两个路段，而是多个如此串联的路段，你也能认识到从s到t的最大流量受限于最小容量的路段。那样的路段，也称为“瓶颈”，别的路段再宽也没有用。在本专栏前两期讨论调度问题时，我们有过一个背景不同但精神上有类似之处的概念，就是“关键路径”，它就是完成任务的瓶颈。下面考虑图2所示的一个稍微复杂一点的例子。
先看图2（a），不妨也看成是一个道路网的抽象。在讨论流问题时，总假设有一个节点是出发点，习惯上用s表示，画在图的最左端，还假设一个节点为到达点，用t表示，画在图的最右端。这个网络中还有另外两个节点a和b，以及节点之间的5条路段，它们的容量也相应标在上面。在图2（a）中，我们还看到有3条从s到t的路径：s—a—t，s—b—t和s—a—b—t。
单位时间里从s到t能发出多少辆车？显然取决于那些车走的路径。如果让它们都走s—a—b—t，如图2（b）所示，那最多是20。此时路段s—b用不上了，因为它后面的b—t已经被占满。不过，如果我们让20辆走s—a，但在a分流，10辆走a—t，10辆走a—b，同时让10辆走s—b—t，就实现了从s到t的最大流量30。图2（c）所示的，是这样一种安排的另一个视角的理解，虚线所表示的相当于是说在图2（b）已经在s—a—b—t安排了流量20的基础上，可以让从s—b来的流量（10）沿着a—b的反方向到達t。这样一种视角和前面说的在a点分流是等价的，它乍听起来不如分流的说法自然，但方便地成为我们后面讨论算法的“思想基础”。
到此，读者应该慢慢体会到这个问题的挑战之处了，如果网络稍微复杂一点，如图3（a）所示，要目测得出源s到目的t之间最大流量的安排绝非易事，因而需要算法。
首先，让我们来一般地理解一下这个问题。给定一个如图3（a）所示的网络，假设需要在每条边上做流量安排，总体体现为从s到t的流量。如果有人说他做了一个如图3（c）的安排（现在每条边上标有两个数，第一个为容量，第二个括弧中的数表示流量安排），你会有什么观感？首先，你会马上说“不靠谱”，因为在a—b边上他安排的是13，要大于网络中a—b的容量12，这是不可接受的。还有没有别的问题？还有一个也是不可接受的问题！注意节点c，进入它的流是12 0 0=12，而离开它的流是3 11=14，二者不相等，是矛盾的。也就是说，任何“可行的”安排必须满足两个条件：①每条边上流量分配不能超过边的容量;②除了出发点s和结束点t外，每个节点的“入流”必须等于“出流”。
现在你可以看看图3（b）了。有什么问题吗？它满足上述两个条件，于是我们说它是一个“可行解”，对应的总流量为11，但我们不知道它是不是“最优解”（即对应s—t之间的最大流安排）。事实上，对这个例子而言，你容易看到沿着s—a—b—t的流量并没有用尽，三条边上分别还剩16-8=8，12-6=6，20-7=13。这意味着你可以对那条路径上的流量给一个增量min（8，6，13）=6。于是得到了一个较优的可行解（此时s—a上的流量为14，a—b上的流量为12，b—t上的流量为13，总流量为17），但还是不知道是否最优。
的确，在此基础上我们进一步还看到一种增加流量的可能，类似于图2（c），此时可以在s—c上增加5，在b—c上减少5，在b—t上增加5，从而得到总流量22。也就是说，如果我们在一个可行解基础上发现一条从s到t的包含两个不同方向边的路径，在顺方向边上的容量剩余，在逆方向边上的流量均大于0，就意味着可以得到一个总流量的提升。
上述在一个可行解的基础上有两种改进思路的例子值得一般性讨论，是本文要介绍的经典Ford-Fulkerson算法（1956年发明）的关键。参考图4，假设在一个可行解基础上发现了一条如图4（a）所示的路径s—a—b—c—d—t，边上的标记x（y）表示容量为x，在当前可行解中已经分配了流量y，那么剩余可用的容量就是x-y。于是我们看到8-3=5，6-5=1，7-2=5，4-3=1和5-1=4，其中的最小值1就是还可以做的改进。边上的标记就更新为8（4），6（6），7（3），4（4）和5（2）。显然，结果依然是一个可行解。
假设发现了一个如图4（b）所示的情况呢？注意a和b之间、c和d之间边的方向是反过来的，因而现在不能说在图中发现了“一条从s到t的（有向）路径”。观察节点a，s—a边产生的入流量为3，b—a边产生的入流量为5，加起来是8。由于是可行解，在a上的入流之和要等于出流之和，因此这个8一定已被与a相关的其他出向边抵消掉了。此时，如果我们让s—a上的流量“ 1”，让b—a上的流量“-1”，不会打破在节点a上的流量平衡，但破坏了节点b上的流量平衡——出流少了1。怎么办？让b—c边上的流量“ 1”就可以了，但这又导致节点c上的入流多了1，解决的办法是让d—c上的流量“-1”，又造成d上的出流少了1，最后就靠在d—t上“ 1”补偿，从而完成整个平衡，得到了一个总流量提高的可行解。值得指出的是，类似于图4（b）的路径上的边不一定非得是正反方向交替的。体会上述分析，我们能认识到关键是保持每个中间节点出入流量的平衡，顺向边的边“ ”，逆向的边“-”。 对图4（b）这个例子而言，其实改进可以比“ 1”更大。但凡需要增加流量的边，不得超过剩余容量，但凡需要减少流量的边，不得超过已分配的流量。因此我们看到8-3=5，5，7-2=5，3和5-1=4，其中的最小值3就是可以得到的最大改进。
综上所述，Ford-Fulkerson算法的基本思想就是从一个每条边流量为0的初始状态（显然是一个可行解）开始，不断发现上述两种改进的机会，直至没有新机会了。
第一种机会，就是要看能否找到一条从s到t的有向路径，其上每一条边的剩余流量都大于0。第二种机会，就是要看能否找到一条从s到t的边方向不一定一致的路径（但一定是离开s，进入t），其上顺边的剩余流量和逆边的流量都大于0。道理上就是这样的，不过后者实施起来会感觉别扭。为此，人们想出了一个好办法：将第二种情况转变为第一种，从而可以统一处理。还是以图4为例，这个办法体现在图4（c）中，我们特别注意其中增加了两条边a—b和c—d，上面标示的容量分别为b—a和d—c边上已分配的流量。这样一来，在原始图上存在一条边方向不一致的路径，就等价于在新的图上存在一条有向路径了。与第一种所有方向一致的情况一道，这样的路径统一称为“增量路径”（augmenting path）。
在程序实现中的具体做法就是，用A表示原始网络，但在算法过程中操作一个所谓剩余容量网络G。最初让G=A，一旦决定G的某条边a—b上要分配一个流量x，那么除了在a—b当前剩余容量上减x，同时也在b—a的容量上加x。这样，在当前可行解上寻找提升流量的机会，就都变成在G上寻找一条从s到t的增量路径问题。我们以前面的图2为例来看这个过程。图5（a）是图2所示网络的邻接矩阵A，也就是初始的G，其中下画线的3个数字对应找到的s—a—b—t路径，我们看到最小值为20。于是做更新，除了每一个数减去20外，在对称的地方（也就是反向边）要加20，于是得到图5（b）。
图5（b）中下画线的3个数字对应找到的是增量路径s—b—a—t，我们看到最小值为10。于是做更新，除了对应每一个数减去10外，在对称的地方要加10，于是得到图5（c）。特别注意到，a—b边上剩余流量的情况，最开始是30，然后是10，现在又变成20了。而b—a边上则是0，20，10，两条边上对应数据之和总是30，即原始网络中边上的容量。这正是两种情况交替出现可能带来的结果。
最后的流量分配在图5（d）中，它是图5（a）中的初始容量减去图5（c）中对应项的结果。
至此，可以说我们已经完成了算法的描述。宏观上即是，用给定的网络A，初始化一个称为剩余容量网络的操作网络G，不断在G上发现从s到t的有向（增量）路径，并按照所定的规则对G进行更新，直到没有s—t路径可以发现了，也就是再也没有提升可行解质量的机会了。
怎么在G上发现是否存在s—t增量路径？G是一个有向图，广度优先搜索和深度优先搜索都可以用于发现两个节点之间有向路径。在本专栏前面的文章中，我们多次用到这两种搜索方法，在此不再单独介绍。下面参照图6给出一个广度优先搜索的程序版本，看看算法的实现。
先看10～18行的主程序部分。它要控制做若干次从S开始的广度优先搜索，每次搜索若达到了目的节点t，就更新剩余流量网络G，然后继续搜索;如果没达到t，就意味着没机会了，结束。结束的时候，最大流的分配方案則由初始网络A和工作网络G中的数据直接给出（见上面讨论的图5例）。其中每次搜索的初始化，除了一般BFS都需要的队列（queue）和访问与否的标记（visited）外，还有两个特殊的针对每一个节点的标记——lead和flowcap。lead用于记录搜索过程中的上层节点，flowcap用于记录从源节点（s）经搜索路径到该节点的“饱和流量”。所谓饱和流量，指的是它与该路径上至少一条边的剩余流量相等。有了lead和flowcap，更新G就十分简单了（因而这里没有提供）。
BFS就是广度优先搜索过程，进入时queue中有源节点s。剩余流量网络G采用了矩阵表示，因而有一个for循环来看哪些节点与当前节点x相连（G[x][i]
研究网络中的流问题可有多个不同的视角和目标追求。本文讨论两个节点之间可能经过的最大流量。我们从简单例子开始，建立讨论这个话题的语境。
图1所示为一个3节点{s，a，t}的有向网络，边上的数字表示能支持的流量（不妨看成是单位时间能通过的车辆数），一般也称为对应边的“容量”。这个例子数据表明s—a边的容量为3，a—t边的容量为2。想象为道路，也就相当于是说s—a路段要比a—t路段宽一些。边的箭头方向则表示“单行线”的方向。
现在的问题是，如果我们要不断从s发出开往t的车，单位时间能发多少辆？几乎不用多想，你马上会认识到3是不行的，最多是2。而且如果有人说1，你则会说每条边的容量都还有剩余，因而流量还可以增加。于是我们说，2就是这个网络中从s到t的最大流量。并且，如果面对的不止两个路段，而是多个如此串联的路段，你也能认识到从s到t的最大流量受限于最小容量的路段。那样的路段，也称为“瓶颈”，别的路段再宽也没有用。在本专栏前两期讨论调度问题时，我们有过一个背景不同但精神上有类似之处的概念，就是“关键路径”，它就是完成任务的瓶颈。下面考虑图2所示的一个稍微复杂一点的例子。
先看图2（a），不妨也看成是一个道路网的抽象。在讨论流问题时，总假设有一个节点是出发点，习惯上用s表示，画在图的最左端，还假设一个节点为到达点，用t表示，画在图的最右端。这个网络中还有另外两个节点a和b，以及节点之间的5条路段，它们的容量也相应标在上面。在图2（a）中，我们还看到有3条从s到t的路径：s—a—t，s—b—t和s—a—b—t。
单位时间里从s到t能发出多少辆车？显然取决于那些车走的路径。如果让它们都走s—a—b—t，如图2（b）所示，那最多是20。此时路段s—b用不上了，因为它后面的b—t已经被占满。不过，如果我们让20辆走s—a，但在a分流，10辆走a—t，10辆走a—b，同时让10辆走s—b—t，就实现了从s到t的最大流量30。图2（c）所示的，是这样一种安排的另一个视角的理解，虚线所表示的相当于是说在图2（b）已经在s—a—b—t安排了流量20的基础上，可以让从s—b来的流量（10）沿着a—b的反方向到達t。这样一种视角和前面说的在a点分流是等价的，它乍听起来不如分流的说法自然，但方便地成为我们后面讨论算法的“思想基础”。
到此，读者应该慢慢体会到这个问题的挑战之处了，如果网络稍微复杂一点，如图3（a）所示，要目测得出源s到目的t之间最大流量的安排绝非易事，因而需要算法。
首先，让我们来一般地理解一下这个问题。给定一个如图3（a）所示的网络，假设需要在每条边上做流量安排，总体体现为从s到t的流量。如果有人说他做了一个如图3（c）的安排（现在每条边上标有两个数，第一个为容量，第二个括弧中的数表示流量安排），你会有什么观感？首先，你会马上说“不靠谱”，因为在a—b边上他安排的是13，要大于网络中a—b的容量12，这是不可接受的。还有没有别的问题？还有一个也是不可接受的问题！注意节点c，进入它的流是12 0 0=12，而离开它的流是3 11=14，二者不相等，是矛盾的。也就是说，任何“可行的”安排必须满足两个条件：①每条边上流量分配不能超过边的容量;②除了出发点s和结束点t外，每个节点的“入流”必须等于“出流”。
现在你可以看看图3（b）了。有什么问题吗？它满足上述两个条件，于是我们说它是一个“可行解”，对应的总流量为11，但我们不知道它是不是“最优解”（即对应s—t之间的最大流安排）。事实上，对这个例子而言，你容易看到沿着s—a—b—t的流量并没有用尽，三条边上分别还剩16-8=8，12-6=6，20-7=13。这意味着你可以对那条路径上的流量给一个增量min（8，6，13）=6。于是得到了一个较优的可行解（此时s—a上的流量为14，a—b上的流量为12，b—t上的流量为13，总流量为17），但还是不知道是否最优。
的确，在此基础上我们进一步还看到一种增加流量的可能，类似于图2（c），此时可以在s—c上增加5，在b—c上减少5，在b—t上增加5，从而得到总流量22。也就是说，如果我们在一个可行解基础上发现一条从s到t的包含两个不同方向边的路径，在顺方向边上的容量剩余，在逆方向边上的流量均大于0，就意味着可以得到一个总流量的提升。
上述在一个可行解的基础上有两种改进思路的例子值得一般性讨论，是本文要介绍的经典Ford-Fulkerson算法（1956年发明）的关键。参考图4，假设在一个可行解基础上发现了一条如图4（a）所示的路径s—a—b—c—d—t，边上的标记x（y）表示容量为x，在当前可行解中已经分配了流量y，那么剩余可用的容量就是x-y。于是我们看到8-3=5，6-5=1，7-2=5，4-3=1和5-1=4，其中的最小值1就是还可以做的改进。边上的标记就更新为8（4），6（6），7（3），4（4）和5（2）。显然，结果依然是一个可行解。
假设发现了一个如图4（b）所示的情况呢？注意a和b之间、c和d之间边的方向是反过来的，因而现在不能说在图中发现了“一条从s到t的（有向）路径”。观察节点a，s—a边产生的入流量为3，b—a边产生的入流量为5，加起来是8。由于是可行解，在a上的入流之和要等于出流之和，因此这个8一定已被与a相关的其他出向边抵消掉了。此时，如果我们让s—a上的流量“ 1”，让b—a上的流量“-1”，不会打破在节点a上的流量平衡，但破坏了节点b上的流量平衡——出流少了1。怎么办？让b—c边上的流量“ 1”就可以了，但这又导致节点c上的入流多了1，解决的办法是让d—c上的流量“-1”，又造成d上的出流少了1，最后就靠在d—t上“ 1”补偿，从而完成整个平衡，得到了一个总流量提高的可行解。值得指出的是，类似于图4（b）的路径上的边不一定非得是正反方向交替的。体会上述分析，我们能认识到关键是保持每个中间节点出入流量的平衡，顺向边的边“ ”，逆向的边“-”。 对图4（b）这个例子而言，其实改进可以比“ 1”更大。但凡需要增加流量的边，不得超过剩余容量，但凡需要减少流量的边，不得超过已分配的流量。因此我们看到8-3=5，5，7-2=5，3和5-1=4，其中的最小值3就是可以得到的最大改进。
综上所述，Ford-Fulkerson算法的基本思想就是从一个每条边流量为0的初始状态（显然是一个可行解）开始，不断发现上述两种改进的机会，直至没有新机会了。
第一种机会，就是要看能否找到一条从s到t的有向路径，其上每一条边的剩余流量都大于0。第二种机会，就是要看能否找到一条从s到t的边方向不一定一致的路径（但一定是离开s，进入t），其上顺边的剩余流量和逆边的流量都大于0。道理上就是这样的，不过后者实施起来会感觉别扭。为此，人们想出了一个好办法：将第二种情况转变为第一种，从而可以统一处理。还是以图4为例，这个办法体现在图4（c）中，我们特别注意其中增加了两条边a—b和c—d，上面标示的容量分别为b—a和d—c边上已分配的流量。这样一来，在原始图上存在一条边方向不一致的路径，就等价于在新的图上存在一条有向路径了。与第一种所有方向一致的情况一道，这样的路径统一称为“增量路径”（augmenting path）。
在程序实现中的具体做法就是，用A表示原始网络，但在算法过程中操作一个所谓剩余容量网络G。最初让G=A，一旦决定G的某条边a—b上要分配一个流量x，那么除了在a—b当前剩余容量上减x，同时也在b—a的容量上加x。这样，在当前可行解上寻找提升流量的机会，就都变成在G上寻找一条从s到t的增量路径问题。我们以前面的图2为例来看这个过程。图5（a）是图2所示网络的邻接矩阵A，也就是初始的G，其中下画线的3个数字对应找到的s—a—b—t路径，我们看到最小值为20。于是做更新，除了每一个数减去20外，在对称的地方（也就是反向边）要加20，于是得到图5（b）。
图5（b）中下画线的3个数字对应找到的是增量路径s—b—a—t，我们看到最小值为10。于是做更新，除了对应每一个数减去10外，在对称的地方要加10，于是得到图5（c）。特别注意到，a—b边上剩余流量的情况，最开始是30，然后是10，现在又变成20了。而b—a边上则是0，20，10，两条边上对应数据之和总是30，即原始网络中边上的容量。这正是两种情况交替出现可能带来的结果。
最后的流量分配在图5（d）中，它是图5（a）中的初始容量减去图5（c）中对应项的结果。
至此，可以说我们已经完成了算法的描述。宏观上即是，用给定的网络A，初始化一个称为剩余容量网络的操作网络G，不断在G上发现从s到t的有向（增量）路径，并按照所定的规则对G进行更新，直到没有s—t路径可以发现了，也就是再也没有提升可行解质量的机会了。
怎么在G上发现是否存在s—t增量路径？G是一个有向图，广度优先搜索和深度优先搜索都可以用于发现两个节点之间有向路径。在本专栏前面的文章中，我们多次用到这两种搜索方法，在此不再单独介绍。下面参照图6给出一个广度优先搜索的程序版本，看看算法的实现。
先看10～18行的主程序部分。它要控制做若干次从S开始的广度优先搜索，每次搜索若达到了目的节点t，就更新剩余流量网络G，然后继续搜索;如果没达到t，就意味着没机会了，结束。结束的时候，最大流的分配方案則由初始网络A和工作网络G中的数据直接给出（见上面讨论的图5例）。其中每次搜索的初始化，除了一般BFS都需要的队列（queue）和访问与否的标记（visited）外，还有两个特殊的针对每一个节点的标记——lead和flowcap。lead用于记录搜索过程中的上层节点，flowcap用于记录从源节点（s）经搜索路径到该节点的“饱和流量”。所谓饱和流量，指的是它与该路径上至少一条边的剩余流量相等。有了lead和flowcap，更新G就十分简单了（因而这里没有提供）。
BFS就是广度优先搜索过程，进入时queue中有源节点s。剩余流量网络G采用了矩阵表示，因而有一个for循环来看哪些节点与当前节点x相连（G[x][i]