快捷搜索:

算法9-6:最大流的应用

最大流算法在现实生活中有着广泛的应用,从数据挖掘到图像处理,都有应用。现实生活中很多事物看起来是不相干的,而实际上只要通过数学建模,其实很多问题本质上都是一样的。

这里举的一些例子很多都是没办法第一眼就看出来,首先要理解最大流算法的模型,其次就是将现实生活中的问题转换成最大流问题从而进行求解。

二分图匹配问题

大学即将毕业了,很多童鞋要去找工作。现在有5个童鞋ABCDE,他们分别投了很多简历,录取情况如下:

    阿里录取了A B C 腾讯录取了A B D E 百度录取了C 网易录取了A C 新浪录取了D E

那么如何分配才能让所有的童鞋都有工作呢?

这就是二分图匹配问题。可以将公司和童鞋看成图论中的顶点,而录取情况看成边。这样,上述这个问题就变成了图论的问题。

那这个问题和最大流有什么联系呢?为了解决这个问题,需要增加两个辅助顶点,如下图所示。

这样,为了让最多的同学得到工作,实际上就是让这个网络的流量达到最大。因此,这个问题本质上就是最大流问题。最后求得的解是这样的。

棒球赛淘汰问题

问题描述:有多个球队之间进行棒球赛,使用的是循环赛制。每个球队目前的比赛状况如下表所示。问哪些球队有可能取得冠军?

这个问题换一种角度解释就是哪些球队已经不可能获得冠军。

解决这个问题时,将团队和团队之间的比赛看成图论中的顶点,场次作为边的容量。这样,这个问题就转换成最大流问题了。

研究现状

最大流问题可以说目前还没有找到一个性能非常好的算法。

下表展示了与最大流问题相关的算法名称以及复杂度。

从图中可以看出目前性能最好的算法复杂度是E^2/logE,还有很多的提升空间。理论上最小的复杂度是E。

上表展示的是最坏情况下的复杂度。现实生活中往往需要平均复杂度比较低的算法。实际应用中用的比较多的是Push-relabel算法,这种算法的复杂度是E sqrtE,具体实现方法参见wiki:

经验分享 程序员 职场和发展