用Ford和Fulkerson的增廣路徑演算法，解決網路中的最大流(flow)以及其衍生問題。

01-27

管道網路中每條邊的最大通過能力（容量）是有限的，實際流量不超過容量。

最大流問題(maximum flow problem)，一種組合最優化問題，就是要討論如何充分利用裝置的能力，使得運輸的流量最大，以取得最好的效果。求最大流的標號演算法最早由福特和福克遜與與1956年提出，20世紀50年Ford、Fulkerson建立的「網路流理論」，是網路應用的重要組成成分。

解決這個問題之前，先看兩個相對簡單的特例：二分圖匹配問題和不相交路徑問題。這兩個問題本來就代表了各種各樣的應用。

和最大流問題思想上一致的是最小切割集的問題。

這兩個問題只要解決一個，另一個也會迎刃而解。

這篇文章的基本理念就是：我們希望經由一個網路，以網路的一邊為起點，另一邊為終點，儘可能多運送某種物質—而對於這些路徑有一些附加條件，比如雙邊匹配，或者以某個單位整數倍進行傳輸。

下面來說第一個問題，二分圖匹配：

我們討論二分圖匹配問題時，通常是指最大化匹配。在這種匹配當中，邊的數量應該是追求最大化的。如果情況允許，我們需要尋找的是一種完美匹配。就是里所有的節點都應存在於這個匹配當中。

上圖是一個二分圖的（不是最大化）匹配（粗體的部分），以及從b到f的增廣路徑（高亮部分）。

然後我們可以開始著手實現解決問題的方法，下面的演算法是一種可能的實現方式。參數X和Y都屬於可以迭代的對象，表示圖G的二分圖匹配。它的運行時間可能並不是非常明顯，因為執行時邊總是被開啟和關閉。但是我們可以確定每次迭代都可以增加一對，所以迭代的數量都是O(n)，其中n為節點的數量。假設有m條邊，那麼對於增廣路徑上的搜索基本上就是對連通分量的遍歷也就是O(m)的複雜度。下面是實現的代碼：

# 通過增廣路徑演算法來尋找最大雙邊匹配nfrom itertools import chainnnndef match(G, X, Y):n H = tr(G)n S, T, M = set(X), set(Y), set()n while S:n s = S.pop()n Q, P = {s}, {}n while Q:n u = Q.pop()n if u in T:n T.remove(u)n breakn forw = (v for v in G[u] if (u, v) not in M)n back = (v for v in H[u] if (v, u) in M)n for v in chain(forw, back):n if v in P:n continuen P[v] = un Q.add(v)n while u != s:n u, v = P[u], un if v in G[u]:n M.add((u, v))n else:n M.remove()n return Mnnndef tr(G):n GT = dict()n for u in G:n GT[u] = set()n for u in G:n for v in G[u]:n GT[v].add(u)n return GTn

這裡的代碼，運行時間為O(mn)。

下面說另一個問題，不相交的路徑：

增廣路徑演算法也可以用來解決相對於尋找圖的匹配來說更加一般化的問題，其中最簡單的就是累計邊的不相交路徑，而不是邊的本身的累計。邊的不相交路徑可以共享節點，但是不能共享邊。

最簡單的是生命兩個特殊的節點s和t，一個是源點，一個是匯點。然後我們要求所有的路徑都從s開始。然後從t結束。

如果每個源點和匯點都只屬於唯一的路徑，如果不用在意拉節點和灌節點之間的配對的話，那麼整個題可以被歸簡為單源點—匯點問題。每次加入一對s、t節點時，就引入了從s到所有源點的邊，以及從所有匯點到t的邊。路徑的數量總是不變的，而重新構造您所要尋找的便只需要重新剪除s和t節點。

對此，我們可以將圖分割為互相都獨立的小圖。然後我們可以加入以下兩個規則：

對於s和t節點以外，每個節點的入邊數量和出邊數量必須相等。
對任何一條邊而言，最多只有一條路徑可以佔用它。

比如，下圖中：

這是一個被發現了一條路徑（加粗的邊），以及一條增廣路徑（高亮的邊）的s-t網路。

第一次迭代時候，第一條路徑被建立了，從s開始，經歷c和b，到達t結束。現在任何其他路徑都被這條路徑阻塞了。但是增廣演算法可以取消c到b的路徑來改進解決方案。

取消操作的工作原理與二分圖匹配差不多完全相同，這裡不再詳細描述。下面是代碼實現：

# 使用帶標記的遍歷來尋找增廣路徑，並對邊不相交的路徑計數nfrom itertools import chainnnndef paths(G, s, t):n H, M, count = tr(G), set(), 0n while True:n Q, P = dict(s), dict()n while Q:n u = Q.pop()n if u in t:n count += 1n breakn forw = (v for v in G[u] if (u, v) not in M)n back = (v for v in H[u] if (v, u) in M)n for v in chain(forw, back):n if v in P:n continuen P[v] = un Q.add(v)n else:n return countn while u != s:n u, v = P[u], un if v in G[u]:n M.add((u,v))n else:n M.remove((v, u))nnndef tr(G):n GT = dict()n for u in G:n GT[u] = set()n for u in G:n for v in G[u]:n GT[v].add(u)n return GTn

這段代碼的每段迭代都包含了一個相對直白的遍歷，運行時間是O(m2)。

下面說下一個問題，最大流問題：

這個問題的通用解決方案當中，一個幼稚的方法是直截了當的對圖中的邊進行分割。然後我們看一下這個技術，然後我們設置兩個規則：

除了s和t節點以外，流入節點的流量與流出節點的流量應該相等。
對於給定的邊，最多只能允許c(e)個單位的流通過

來看一張圖：

上圖是用偽節點方法來模擬邊的容量。

c(e)是邊e的容量。

然後繼續看下面的圖：

在第一個狀態當中，流從s-c-b-t節點依次經過，並且流的值為2.這個流阻塞了其他所有沿著入邊的改進。

不過，增廣路徑包含了反向的邊。通過取消從c到b的一個單位的流，我們就可以從c經過d到t增加一個額外的單位，於是我們達到了最大流。

然後看具體的實現代碼：

# 通過BFS與標記法來尋找增廣路徑nfrom collections import dequeninf = float(inf)nnndef bfs_aug(G, H, s, t, f):n P, Q, F = {s: None}, deque([s]), {s: inf}nn def label(inc):n if v in P or inc <= 0:n returnn F[v], P[v] = min(F[u], inc), un Q.append()n while Q:n u = Q.popleft()n if u == t:n return P,F[t]n for v in G[u]:n label(G[u][v] - f[u, v])n for v in H[u]:n label(f[v, u])n return None, 0n

然後是Ford-Fulkerson演算法：

# Ford-Fulkerson法（默認使用Edmonds-Karp演算法）nfrom collections import defaultdictnnndef ford_fulkerson(G, s, t, aug=bfs_aug):n H, f = str(G), defaultdict(int)n while True:n P, c = aug(G, H, s, t, f)n if c == 0:n return fn u = tn while u != s:n u, v = P[v], un if v in G[u]:n f[u, v] += cn else:n f[v, u] -= cnnndef tr(G):n GT = dict()n for u in G:n GT[u] = set()n for u in G:n for v in G[u]:n GT[v].add(u)n return GTn

下面一個部分，我們說一下最小切割集的問題：

這個問題其實可以用Ford-Fulkerson演算法實現。

這裡簡要證明，我們假設目前所談論的s-t切割發是這裡的唯一的切割方法，然後將該切割集的容量定義其中所通過的流量，這樣我們會發現以下三個命題是等價的：

我們已經找到了規模為k的流，並且存在一個容量為k的切割集。
我們已經找到了最大流。
圖中而沒有增廣路徑。

這三個命題其實並不難證明，這裡不再給出。

下面說最後一個問題，最小成本的流和賦值問題：

解決這個問題的辦法，其實是一個貪心演算法。我們逐漸建立一個流，每一次迭代中儘可能地增加一些成本。至於這個演算法可行性的證明，這裡不再給出了。

這裡直接給出實現的代碼：

# Busacker_Gowen演算法，使用Bellman-Ford作為增廣演算法ndef busacker_gowen(G, W, s, t):nn def sp_aug(G, H, s, t, f):n D, P, F = {s: 0}, {s: None}, {s:inf, t:0}nn def label(inc, cst):n if inc <= 0:n return Falsen d = D.get(u, inf) + cstn if d >= D.get(u, inf):n return Falsen D[v], P[v] = d, un F[v] = min(F[u], inc)n return Truenn for _ in G:n changed = Falsen for u in G:n for v in G[u]:n changed |= label(G[u][v] - f[u, v], W[u, v])n for v in H[u]:n changed |= label(f[v, u], -W[v, u])n if not changed:n breakn else:n raise ValueError(negative cycle)n return P, F[t]n return ford_fulkerson(G, s, t, sp_aug)n

對於演算法的運行時間來說，Busacker_Gowen演算法的運行時間取決於所選擇的最短路徑演算法。

到這裡，這篇文章到這裡就要結束了，生活中還是工程中經常會遇到這一章的問題衍生問題。比如棒球淘汰問題、議員選舉問題、節假日醫生問題、供給與需求的問題和一致性矩陣取整問題等等。

這篇文章主要寫的，就是一個核心問題，找到網路中的最大流。基本上所有的解決方案總體思路都是不斷迭代改進，不斷重複地尋找一條增廣路徑，讓我們的解決方案更優。

寫到這裡，文章就要結束了。

今天是雙十一，作者今天下午參加了一個Google DevFest的活動。也有些收穫。作者比較喜歡開源，如果有這個愛好的朋友，大家可以一起交流。

今天的溫度，驟然降低，希望大家多穿衣服，注意保暖。

謝謝大家關注。希望大家每天都能進步。