s-t Flow
所謂伊人,在水一方。溯洄從之,道阻且長;溯游從之,宛在水中央。《詩經.蒹葭》
Flow Network
把一張圖想成是水流管線圖。圖上的邊想成是水管:邊的權重想成是水管的容量上限(容量下限預設為零),有向邊僅允許單向流動,無向邊得同時雙向流動。圖上的點想成是水管的接合點,並附有控制水流流向與流量的機器:點的權重想成是接合處的容量上限(容量下限預設為零),但是大家一般都不考慮點的權重。
每一條管線的流量數值與容量上限數值,以一斜線區隔,標記於圖上各條邊,方便觀看。水流流動時必須遵守各條管線的容量限制,不得有逾越容量限制之情事。流量數值與容量上限數值一定是正值或零,不得為負值。
在這張水流管線圖當中,水流流速是穩定的、是源源不絕的,有變化的只有水流流向與流量。因此,水流流動時,只要關心各條管線的方向限制和容量限制就可以了。
當一張圖專門用於水流流動時,則可稱之為Flow Network,中譯為「流網路」。
「流網路」只有容量資訊,沒有流量資訊。
s-t Flow
在圖上選定一個源點(source,標記為s)和一個匯點(sink,標記為t),源點灌水,匯點泄水,並控制水流從源點流至匯點,中途不得滲漏、不得淤滯。
s-t Flow以下簡稱為「流」。一個流便是由源點經管線至匯點的水流。一個流的流量,即是源點灌入的水流流量,同時也是匯點泄出的水流流量。
「流」只有流量資訊,沒有容量資訊。
Maximum s-t Flow
「最大流」。給定一張圖,以及給定一個源點與一個匯點,所有可能的Flow當中,流量最大者便是Maximum Flow,可能會有許多個。
在源點一口氣灌入大量的水,藉由調整各條管線的流量與流向,讓匯點泄出的流量最多。
Minimum s-t Flow
「最小流」。一滴水都不流,管線裡都沒水,就是Min-Flow,流量為零。大家應該都懂,所以就討論到這裡了。
圖例:不屬於流的玩意
水流流到無法流動的地方,水流淤滯而無法流至匯點,不能稱作流。
圖例:合流、分流、交流
水流可以在任何點上合流、分流、交流──簡單地來說,就是每個點之中,流入與流出的水量要相等,至於要怎麼分合都無所謂。
圖例:產生迴圈的流
產生迴圈的流會佔據管線容量,令流量難以再增加,是一種浪費。
圖例:源點與匯點在一起的流
感情很好的兩個點,一般視作內地裡波濤洶湧,表面上流量為零。
多個源點變成一個源點、多個匯點變成一個匯點
先前都只討論一個源點和一個匯點的原因,其實是因為多個源點可以轉化成一個源點、多個匯點可以轉化成一個匯點。當圖上有多個源點時,就在圖上新增一個超級源點,連向這些源點,邊的容量都設定為無限大。如此一來,就可以只留下一個超級源點,並取消原本的源點了。匯點的道理亦同。
因此,在s-t Flow當中,多個源點和多個匯點可以改為一個源點和一個匯點,最後只討論一個源點和一個匯點就可以了。事情也變簡單多了。
點的容量變成邊的容量
先前提到大家一般不考慮點的容量,其實是因為點的容量可以轉化為邊的容量。把P點改成兩個點Pin和Pout,原先連到P點的邊變成連到Pin,由P點連出的邊變成由Pout連出,P點的容量則由一條Pin到Pout的邊來取代之。
因此,在s-t Flow當中,點的容量可以改為邊的容量,最後只要考慮邊的容量就行了。只考慮邊的容量,事情也變簡單多了。
多重的邊變成單獨的邊
無向圖中,當兩點之間有多重的邊,就可以加總這些邊的容量限制,合併成單獨的邊;有向圖中,當一點到另一點有多重的邊,就可以加總這些邊的容量限制,合併成單獨的邊。
因此,在s-t Flow當中,多重的邊可以改為單獨的邊,最後只討論「無向圖:兩點間僅有一條邊、有向圖:一點到另一點僅有一條邊」就可以了。事情也變簡單多了。
來回水流變成單向水流
兩點之間,兩條方向相反的有向邊,等量減少來向與回向的水流,不會影響總流量,也不會違背規則。
因此,在s-t Flow當中,來回水流可以變成單向水流,最後只要從中選擇一條邊來流動就可以了。事情也變簡單多了。
無向邊變成有向邊
無向邊得同時雙向流動。一條無向邊可以改為兩條方向相反的有向邊,可是必須共用容量。
由於來回水流可以變成單向水流,所以上述兩條方向相反的有向邊,其實不必共用容量,宛如普通的有向邊。
因此,在s-t Flow當中,一條無向邊可以變成兩條方向相反的有向邊,最後只討論有向邊就可以了。事情也變簡單多了。
Max-Flow Min-Cut Theorem
一條涓流的流量與瓶頸
水從源點流至匯點,中途不會滲漏、不會淤滯。一條由源點流至匯點的小小涓流,其流動路徑當中,每一條邊的流量,都會是小小涓流的流量。
水流流動時要符合管線容量限制。一條由源點流至匯點的小小涓流,其流量的瓶頸,會是流動路徑當中,容量上限最低的一條邊。
一個流的總流量與瓶頸(一)
水從源點流至匯點,中途不會滲漏、不會淤滯。現在把圖上的點,依地理位置劃分作兩區,一區鄰近源點,另一區鄰近匯點──一個從源點流至匯點的流,「由源點流至匯點的總流量」會等於「由源點區流入到匯點區的總流量」減去「由匯點區流回到源點區的總流量」。無論是哪一種分區方式,都有這種性質。
水流流動時要符合管線容量限制。一個從源點流至匯點的流,「由源點區流入到匯點區的總流量」會小於等於「由源點區橫跨到匯點區的管線總容量」。反方向亦同。
也就是說,一個從源點流至匯點的流,其總流量的瓶頸,會出現在「由源點區橫跨到匯點區的管線總容量」最低的一種分區方式。
一個流的總流量與瓶頸(二)
【讀者若不懂s-t Cut,請見本站文件「Cut」。】
方才的分兩區方式有點籠統,很難定義誰鄰近源點,誰鄰近匯點,因此計算學家嘗試以s-t Cut來取代方才的說法,希望藉由s-t Cut把事情說得更嚴謹一些。然而事情也稍微變得複雜了。
水從源點流至匯點,中途不會滲漏、不會淤滯。現在把圖上的點,利用s-t Cut的概念劃分作兩側,一側包含源點,另一側包含匯點──一個從源點流至匯點的流,「由源點流至匯點的總流量」會等於「由源點側流入到匯點側的總流量」減去「由匯點側流回到源點側的總流量」。無論是哪一種劃分方式,都有這種性質。
水流流動時要符合管線容量限制。一個從源點流至匯點的流,「由源點側流入到匯點側的總流量」會小於等於「由源點側橫跨到匯點側的管線總容量」。反方向亦同。
也就是說,一個從源點流至匯點的流,其總流量的瓶頸,會出現在「由源點側橫跨到匯點側的管線總容量」最低的一種分區方式。也就是容量的Minimum s-t Cut。
Max-Flow Min-Cut Theorem
「最大流最小割定理」其實就是談瓶頸。「網路流量的最大s-t流」等於「管線容量的最小s-t割」,管線若還有空間,就儘量增加流量,直到遇到瓶頸,瓶頸會出現在容量的最小s-t割。
打個比方來說,在一個裝水的塑膠袋底部戳洞,水就會流出來;戳越多洞,水就流出的越多。這表示水一旦有隙可乘,就一定會源源而來、滔滔而至,乃增加流量。水一旦無隙可乘,流量達到上限,此刻就是最大流了。
要找最大流,可以運用「最大流最小割定理」的概念,讓水流不停地鑽空隙流至匯點,當無法再找到空隙時,就是極限了,就是最大流了。
若只找最大流流量,則可以運用求最小s-t割的演算法,計算管線容量的最小s-t割的權重,即是最大s-t流流量。
Maximum s-t Flow: Augmenting Path Algorithm(Ford-Fulkerson Algorithm)
用途
給定一張圖,並給定源點、匯點,找出其中一個最大流。
Flow Decomposition
一個流是由許多條小小涓流逐漸聚集而成的。我們可以用一條一條的小小涓流,累積出最大流。
溯洄沖減
【註:此概念目前尚未有專有名詞】
然而有些涓流的路徑不理想,浪費了管線空間。有鑒於此,演算法作者設計了一個手法:溯洄沖減。流出第一條涓流之後,第二條涓流可以溯洄上一條流的部份路段,然後到達匯點。正流與逆流相互沖減的結果,使得相互交織的兩條涓流,成為兩條獨立的涓流。如此一來,就算涓流的路徑不理想,之後仍可靠溯洄沖減來調整路徑。
【註:涓流、溯洄、沖減這三個詞,是初次使用。我查字典後,覺得意義相近,而選用的。而且它們都是水字旁!】
溯洄沖減的時候,可以選擇水量多寡和路線位置,藉以調整成不同的流。
溯洄沖減的概念可以用於許多地方。這裡列出一些相關問題,供各位練習。
UVa 10806 10380
Residual Network
每次增加一條小小涓流,都要時時刻刻遵守各條管線的容量限制。管線要有剩餘空間,或者管線有溯洄沖減的機會,涓流才能流過管線。
一個便捷的整合方式是:管線的剩餘空間、再加上可供溯洄沖減的水量,稱作「剩餘容量Residual Capacity」;所有管線的剩餘容量,整體視作一張圖,稱作「剩餘網路Residual Network」。
如此一來,涓流要進行流動,只要參考剩餘網路,遵守各條管線的剩餘容量限制就可以了。
剩餘網路是一個高度抽象概念,為的是整合涓流流動的容量限制。實作程式碼時,可以直接建立一個剩餘網路的資料結構,隨時利用容量與剩餘容量來計算流量。
Augmenting Path
「擴充路徑」,剩餘網路上面一條由源點到匯點的路徑。換個角度想,把握管線的剩餘空間,把握溯洄沖減,找出一條由源點到匯點的小小涓流路徑,就是一條擴充路徑。
擴充路徑是一條可以擴充總流量的路徑,擴充的流量可多可少,一般來說流量越多越好,到達瓶頸最好,能較快達到最大流。
擴充路徑的長度範圍是1到V-1(長度為0表示源點與匯點重疊)。當一條擴充路徑超過V-1條邊,則會形成浪費管線容量的迴圈,此時應消除迴圈之後,才來做為擴充路徑。
演算法
不斷找擴充路徑,並擴充流量。直到沒有擴充路徑為止。 所有擴充路徑總合起來,就是最大流。 所有擴充路徑的流量總和,就是最大流流量。 擴充路徑要怎麼找都可以, 不一樣的擴充路徑有機會產生不一樣的最大流。
還找得到擴充路徑: 表示目前不是最大流,因為藉由擴充路徑,還可以再增加總流量。 找不到擴充路徑: 表示源點往匯點方向的一些關鍵管線已經沒有剩餘容量。沒有剩餘容量則表示: 甲、管線沒有剩餘空間(或根本沒有管線),也就是遭遇瓶頸。 乙、不能溯洄沖減。 根據最大流最小割定理,遭遇瓶頸時即是最大流。 【註:這部分的證明有漏洞。沒有考慮到形成迴圈的涓流。】
這個演算法的絕妙之處,是導入了溯洄沖減的機制,藉以調整流動路徑;然後把溯洄沖減併入了容量限制的思維,創立剩餘網路、擴充路徑等抽象概念;最後返回到最大流最小割定理,間接證明了溯洄沖減無論在什麼情況下,都能調整好流動路徑,找出最大流──調校水流的本質,就是剩餘網路。
另外可以發現,在整個過程當中,所有管線的剩餘容量的總和是固定不變的──只是源點往匯點方向的剩餘容量越來越少,匯點往源點方向的剩餘容量越來越多。整個過程可以看作是在調整剩餘網路的勢力走向──每次以擴充路徑擴充流量後,正方向會減少對應的剩餘容量,逆方向會增加對應的剩餘容量,源點與匯點之間的勢力差距越來越大。
時間複雜度
找一條擴充路徑,等同一次Graph Traversal的時間。
最差情況下,擴充路徑流量通通都是1,共找到F條,F是最大流的流量。
圖的資料結構使用Adjacency Matrix,便是O(V²F);圖的資料結構使用Adjacency Lists,便是O((V+E)F),通常簡單寫成O(EF)。
如何記錄容量、流量、剩餘容量
為了實現溯洄沖減的概念,要是兩點之間只有單獨一條有向邊,就添配一條反向邊,讓雙向都有邊;要是兩點之間已經是兩條方向相反的有向邊,就不必更動;要是兩點之間是一條無向邊,則改成兩條方向相反的有向邊。
每一條邊的容量是定值;至於流量與剩餘容量,則有三種不同的記錄方式。第一種方式最直覺。第二種方式中庸。第三種方式最精簡,實作簡單,不過最後要計算最大流的時候會比較麻煩。
第一種記錄方式。先前提到,兩條方向相反的有向邊,可以只讓一條邊擁有水流,另一條邊則沒有水流。在此利用沒有水流的那條邊:兩點之間其中一個方向是正流量,是真正流動的方向;另一個方向則是虛設的負流量,用來增加剩餘容量以利溯洄沖減。
一開始還沒有水流的時候: flow(i, j) = 0; flow(j, i) = 0; 有一條涓流經過邊ij之後: flow(i, j) += 流量; flow(j, i) -= 流量; 有一條涓流經過邊ij,又有一條涓流溯洄沖減,經過邊ji之後: flow(i, j) = flow(i, j) + 流量1 - 流量2; flow(j, i) = flow(j, i) - 流量1 + 流量2;
最後可歸納得出,當一條涓流經過邊ij的時候: flow(i, j) += 流量; flow(j, i) = -flow(i, j); 真正的流量則是正流量: true_flow(i, j) = max(flow(i, j), 0); true_flow(j, i) = max(flow(j, i), 0); 剩餘容量以管線的容量上限和流量相減而得: residue(i, j) = capacity(i, j) – flow(i, j); residue(j, i) = capacity(j, i) – flow(j, i);
第二種記錄方式。只要有涓流經過了管線,就把涓流流量直接累加在管線流量。雖然這種記錄方式會讓流量違背容量限制,可是在剩餘容量正確的情況下,還是能找出最大流。
令邊ij是一條由i點到j點的邊。令邊ji是一條由j點到i的邊。 一開始還沒有水流的時候: flow(i, j) = 0; flow(j, i) = 0; 有一條涓流經過邊ij之後: flow(i, j) += 流量; flow(j, i) 保持不變; 有一條涓流經過邊ij,又有一條涓流溯洄沖減,經過邊ji之後: flow(i, j) += 流量1; flow(j, i) += 流量2;
最後可歸納得出,當一條涓流經過邊ij的時候: flow(i, j) += 流量; flow(j, i) 保持不變; 真正的流量是把雙向流量等量減少後而得(去掉溯洄沖減的部分): true_flow(i, j) = flow(i, j) - min(flow(i, j), flow(j, i)); true_flow(j, i) = flow(j, i) - min(flow(i, j), flow(j, i)); 剩餘容量以管線的容量上限和雙向流量計算而得: residue(i, j) = capacity(i, j) – (flow(i, j) - flow(j, i)); residue(j, i) = capacity(j, i) – (flow(j, i) - flow(i, j));
第三種記錄方式。是第一種記錄方式的相反面向,主角改為剩餘容量,只要有涓流經過了管線,正方向剩餘容量會減少,反方向剩餘容量會增加。
令邊ij是一條由i點到j點的邊。令邊ji是一條由j點到i的邊。 一開始還沒有水流的時候: residue(i, j) = capacity(i, j); residue(j, i) = capacity(j, i); 有一條涓流經過邊ij之後: residue(i, j) -= 流量; residue(j, i) += 流量; 有一條涓流經過邊ij,又有一條涓流溯洄沖減,經過邊ji之後: residue(i, j) = residue(i, j) - 流量1 + 流量2; residue(j, i) = residue(j, i) + 流量1 - 流量2;
最後可歸納得出,當一條涓流經過邊ij的時候: residue(i, j) -= 流量; residue(j, i) += 流量; 真正的流量以管線的容量上限和剩餘流量相減而得,而且是正流量: true_flow(i, j) = max(capacity(i, j) – residue(i, j), 0); true_flow(j, i) = max(capacity(j, i) – residue(j, i), 0);
找出一個最大流+計算最大流的流量
Maximum s-t Flow: Shortest Augmenting Path Algorithm(Edmonds-Karp Algorithm)
演算法
Augmenting Path Algorithm改良版。擴充路徑是源點到匯點的最短路徑(管線長度皆為1),並且擴充流量至瓶頸。這種方式可以避免浪費管線空間,避免反覆地溯洄沖減,更快找到最大流。
不斷找最短擴充路徑,直到找不到為止,即得最大流。 最多找VE次就能達到最大流。
達到最大流,需要的最短擴充路徑數量。
(Edge Labeling with Shortest Distance)
剩餘網路的每一條邊,皆標記一個距離數值,數值大小是源點到該邊的最短距離。
以最短路徑擴充流量至瓶頸,某些邊的距離數值會增加,沒有任何一條邊的距離數值會減少。宏觀來看,距離數值與日俱增。
擴充路徑是最短路徑。瓶頸之處,新增的反向邊,比起原先的正向邊,距離數值至少多一。從彼端繞過來一定比較遠。
瓶頸正向邊:距離數值增加,變成無限大。(水滿了,從剩餘網路之中消失。) 瓶頸反向邊:距離數值不變,比正向邊至少多一。(原先就有反向邊。) 距離數值增加,比正向邊至少多一。(原先沒有反向邊,新增反向邊。) 其餘的邊:距離數值不變。(瓶頸斷掉,但是有替代路線。或者尚未遭遇瓶頸。) 距離數值增加。(瓶頸斷掉,繞遠路。)
甲、最差情況下,每次擴充流量,整體距離數值只增加1。乙、圖上總共E條邊,每條邊的距離數值範圍為0到V-1。因此至多VE條最短擴充路徑,就能達到最大流。
達到最大流,需要的最短擴充路徑數量。
(Vertex Labeling with Shortest Distance)
剩餘網路的每一個點,皆標記一個距離數值,數值大小是源點到該點的最短距離。
每次以最短路徑擴充流量至瓶頸之後,最短路徑上的點的距離數值不見得會增加;源點到該點的所有最短路徑們通通截斷之後,距離數值才會增加。因此這種方式估計不出結果!
時間複雜度
以BFS尋找O(VE)條擴充路徑的時間。
圖的資料結構使用Adjacency Matrix,便是O(V³E);圖的資料結構使用Adjacency Lists,便是O((V+E)VE),通常簡單寫成O(VE²)。
找出一個最大流+計算最大流的流量
計算最大流的流量
UVa 820 10330 10779 563 10511 10983
Maximum s-t Flow: Blocking Flow Algorithm(Dinic's Algorithm)
抽刀斷水水更流。《李白.宣州謝朓樓餞別校書叔雲》
演算法
Shortest Augmenting Path Algorithm改良版。一口氣找到一樣長的最短擴充路徑們。
重覆以下動作最多V-1次,直到無法擴充流量: 1. 計算residual network各點到源點(匯點)的最短距離。 2. 建立admissible network。 3. 尋找blocking flow,並擴充流量。
Admissible Network
剩餘網路上面,以源點(匯點)作為起點,計算源點(匯點)到每一點的最短距離。
剩餘網路上面,一條由源點往匯點方向的邊、兩端點最短距離相差一,稱作「容許邊Admissible Edge」。所有容許邊,整體視作一張圖,稱作「容許網路Admissible Network」。
容許網路是有向無環圖(DAG)、分層圖(Level Graph)。容許網路可以畫成一層一層的模樣,只有相鄰的層有邊。
容許網路就是剩餘網路的「最短路徑圖」。
容許網路上面,任意一條由源點到匯點的路徑,都是最短擴充路徑。藉由容許網路,可以迅速找到一樣長的最短擴充路徑們。
Blocking Flow
容許網路上面,一個源點到匯點的流,無法再擴充流量,稱作「阻塞流」,通常有許多種,也不必是最大流。
容許網路上面,逐次找到一樣長的最短擴充路徑們,並且每次都讓擴充的流量到達瓶頸,直到找不到為止;整體形成阻塞流。
演算法:找出一個阻塞流
容許網路上面,尋找最短擴充路徑,不必溯洄沖減。溯洄沖減會增加路徑長度,最後得到的不是最短擴充路徑。
由源點隨意往匯點走,若遇到死胡同,就重頭開始走,下次避免再走到死胡同。若順利走到匯點,就形成一條最短擴充路徑,並且擴充流量。
改由匯點隨意往源點走,就不會遇到死胡同。
一條最短擴充路徑,至少有一條邊是瓶頸。容許網路最多只有E條邊能作為瓶頸,所以一個阻塞流最多只有E條最短擴充路徑。
從源點走到匯點並擴充流量需時O(V),最多有O(E)條最短擴充路徑,所以找出一個阻塞流的時間複雜度是O(VE)。
另外,使用「Link-Cut Tree」記錄容許網路,時間複雜度可以加速到O(ElogV)。
達到最大流,需要的阻塞流數量。
(Vertex Labeling with Shortest Distance)
前面章節利用Vertex Labeling with Shortest Distance估計不出結果,這裡卻可以。
剩餘網路上面,以阻塞流擴充流量,就斷絕了所有一樣長的最短擴充路徑。
容許網路上面,所有由源點到匯點的最短路徑們都阻塞了。剩餘網路上面,源點到匯點的最短距離會增加,下次的最短擴充路徑會更長;擴充流量而新增的反向邊,也不會減少源點到匯點的距離。
擴充路徑的長度範圍是1到V-1(長度為0表示源點與匯點重疊)。因此最多找V-1次阻塞流,就一定沒有擴充路徑了。
時間複雜度
找一個阻塞流需時O(VE),最多找O(V)次,總時間複雜度O(V²E)。
找出一個最大流+計算最大流的流量
UVa 10546
延伸閱讀:Malhotra-Kumar-Maheshwari Algorithm
http://www.cs.cornell.edu/Courses/cs4820/2013sp/handouts/DinicMPM.pdf
容許網路上面,定義一個節點的容量是min(所有出邊總和, 所有入邊總和),容量最小的節點即是瓶頸。
尋找阻塞流,不斷找到擴充路徑經過瓶頸(切兩段,先往源點找、再往匯點找),使用Binary Heap找瓶頸為O(V²logV);使用Fibonacci Heap找瓶頸為O(V²)。找V次阻塞流為O(V³)。
Maximum s-t Flow: Capacity Scaling Algorithm
演算法
容量視作二進位數字,從最高數量級開始,每回合添加一個位數,並且擴充流量。
重複以下步驟logC回合: 1. 每條邊容量翻倍:流量隨著翻倍。 2. 每條邊容量加零或加一。 3. 尋找擴充路徑(或擴充流),填滿多出的容量,達到最大流。
時間複雜度
甲、總共logC回合。C是最大的管線容量。
乙、每回合開始之前,源點到匯點的剩餘容量已經填滿。每回合當中,添加到圖上各條邊的容量只有0或1,剩餘容量頂多增加E,流量頂多擴充E。換句話說,每回合至多E條擴充路徑,就能達到最大流。
丙、找一條擴充路徑,等同一次Graph Traversal的時間。
圖的資料結構使用Adjacency Matrix,便是O(V²ElogC);圖的資料結構使用Adjacency Lists,便是O((V+E)ElogC),通常簡單寫成O(E²logC)。
計算最大流的流量
Maximum s-t Flow: Preflow, Push, Relabel
壹、push
想像一下:於源點放入足夠水量,然後用力推擠源點,就像針筒注射、發射水槍一樣,讓源點的水一股作氣鑽過整個流網路,最後從匯點噴出水流。
受限於流網路的管線容量瓶頸,水流流量是有上限的。水鑽過流網路的路線,就是一個最大流。匯點噴出的水流流量,就是最大流的流量。
然而電腦程式無法直接實現「一股作氣鑽過整個流網路」,電腦程式只能一個一個算、一步一步算,所以我們只好一個一個點慢慢推進:首先推進源點的水到其它中繼點,再繼續推進中繼點的水到其他中繼點,一個接著一個點慢慢地推進到匯點。
貳、excess和overflowing
為了實現「一個接著一個點慢慢地推進」的想法,便定義圖上每個點都可以儲存水,成了「含水點」,其儲存水量稱作「含水量」。水被推到點上,得以暫時儲存在點上,以後隨時可以繼續推進。
建立含水點、含水量的系統之後,推進順序也無所謂了,因為水一直存在、不會消失,就算推歪方向,也可以往回推,回復原始狀態。
以「含水點」、「含水量」,設計一套找出最大流的方法: 子、先將源點的含水量設定成無限大。 丑、推進源點的水到圖上其他點,慢慢推向匯點,推進順序可隨意。 寅、多餘的水量,會受限於管線容量瓶頸,而留在源點和中繼點上。 卯、最後能夠推進到匯點的水量,就是最大流的流量。
參、residual capacity
推進的同時也記錄管線流量,便可以知道水流流動的情形。管線流量與剩餘容量的概念請參考前面的Augmenting Path Algorithm章節。
推進一個點的水,甲、要注意點的含水量,乙、注意管線的剩餘容量,丙、盡量填滿管線,營造出針筒注射、發射水槍的效果。
肆、admissible edge
「一個接著一個點慢慢地推進到匯點」,要確保各點的水是確實地推向匯點、聚集在匯點,避免漫無目的來回推進,避免環狀推進、不斷繞圈圈。因此導入了「水往低處流」的想法。
以「水往低處流」來設計方法、解決問題: 子、推向匯點:源點高、匯點低、其他點排好適當的高低順序。 丑、由源點漫溢:源點是最高點。 寅、朝匯點聚集:匯點是最低點。 卯、避免繞圈圈:不能推水到一樣高的點。只能推水到更低的鄰點。
伍、height label
為了實現「水往低處流」的想法,便定義圖上每個點都有一個「高度值」,並排好高低順序,由高往低推進、由源點向匯點推進。
高低順序有兩種安排方式:甲、反轉所有邊之後,以匯點為起點的最短路徑長度,作為高度值。乙、以源點為起點的最短路徑長度,取負值(可再加常數變成正值),作為高度值。
採用甲有個好處,因為推進規則可以改成:推進一個點的水,只能到、也只需要到「比此點剛好低一層」的鄰點。如此可以讓推進規則變得單純、容易實作,也依舊保持著水往低處流的原則。
排好高低次序,以及改變推進規則後,會出現新麻煩:甲、匯點不是最低點。乙、源點的水可能會推不出去。丙、現在要是推歪方向,就不能往回推了。丁、朝向匯點的管線容量不足時,一個點將會水洩不通。必須尋找其他管線,才能流向匯點。
以下將一一解決這些問題。
陸、source and target
無論是哪一種高低順序安排方式,都不能保證源點最高、匯點最低。採用甲,可以把源點的高度另設為V-1,源點就一定比圖上其他點高;匯點的高度維持為零,匯點就一定比圖上其他點低。V是圖上的點數。
柒、preflow
源點的高度設為V-1,推進又只能到「比此點剛好低一層」的鄰點,這造成一開始的時候,可能無法推進源點的水到所有鄰點,或說源點的水可能無法流到所有鄰點。
為了解決這種狀況,一開始的時候,就預先推進源點的水到所有鄰點,稱作「預流」。
捌、relabel
另外又追加了「抬高」的想法:當一個含水點水洩不通,就稍微抬高它,讓水可以流過其他管線,到達其他鄰點;甚至可以抬高到往回流,矯正水流流向。
現在不必預先設定每個點的高低次序了,只需固定源點和匯點的高度,讓各個點抬高後總是比源點低、比匯點高即可。想要推動一個含水點的水,就抬高此點;抬高一個含水點,就可以推動此點的水。
以「水往低處流」和「抬高含水點」來設計方法、解決問題: 子、推向匯點:抬高一個點到比匯點還高,但不能抬高匯點。 丑、由源點漫溢:源點是最高點,高度設為V-1,並預流。 寅、朝匯點聚集:匯點是最低點,高度設為0。 卯、避免繞圈圈:不能推水到一樣高的點。只能推水到剛好低一層的鄰點。 辰、避免水洩不通:抬高一個點比鄰近的點還高,以紓解積水。 巳、矯正流向:抬高一個點比來源的點還高,以豆退嚕。
玖、saturating push
如果一個含水點有許多鄰點,就先抬高含水點稍高於最低的鄰點,並推水到最低的鄰點,並盡量令管線滿溢;如果還有剩水,就再抬高含水點稍高於次低的鄰點,並推水到次高的鄰點,依此類推。以匯點的角度來看,朝向匯點的各條管線會陸陸續續流過水流並且滿溢,最後就會得到最大流。各位可以觀察看看。
當一個含水點水洩不通,表示下游已經遭遇瓶頸、或說下游管線已經滿溢(甚至根本沒有管線)、或說沒有剩餘容量、或說無法再推更多水到匯點、或說有多餘的水流不到匯點。
當一個含水點水洩不通,就抬高含水點,讓水往回流,矯正流向,替多餘的水,尋求其他出路,流到匯點。相反的,當一個含水點河涸海乾時,就沒有必要抬高此點,找自己麻煩。
拾、retreat(沒有專用術語,故自行命名)
當水量過剩,又不斷抬高圖上每個點,最後圖上每個點都會比源點還高,所有剩水都會回歸源點。這剛好可以作為演算法的閉幕。此時圖上的水流流動情形就是最大流。
以「水往低處流」和「抬高含水點」來設計方法、解決問題: 子、推向匯點:抬高一個點到比匯點還高,但不能抬高匯點。 丑、回歸源點:抬高一個點到比源點還高,但不能抬高源點。 寅、由源點漫溢:源點是最高點,高度設為V-1。 卯、朝匯點聚集:匯點是最低點,高度設為0。 辰、避免繞圈圈:不能推水到一樣高的點。只能推水到剛好低一層的鄰點。 巳、避免水洩不通:抬高一個點比鄰近的點還高,以紓解積水。 午、矯正流向:抬高一個點比來源的點還高,以豆退嚕。
小結
欲讓水「一股作氣鑽過整個流網路」計算最大流,電腦卻只能「逐點推進」,只好製作一些中繼的「含水點」,加入「水往低處流」的概念,以匯點為起點的最短路徑長度設定「高低次序」,迫使水流向匯點。但是卻導致「源點不是最高點」、「源點無法推水」、「無法矯正流向」、「水洩不通」等諸多問題。於是又出現了「設定源點匯點高度」、「預流」、「抬高」的想法,解決了上述問題,從此亦不再需要安排「高低次序」。至於無法推到匯點的剩水,恰可藉由「抬高」而回歸源點,演算法完美結束。
接下來開始詳細列出演算法內容。
Preflow
推動源點的水到所有鄰點。 (源點可以不必設定水量,不影響結果。)
Push
給定一個含水點和一個與其相鄰的點,推水過去。 以下是允許進行Push的條件,確定符合後才得進行Push: 壹、含水點不是源點和匯點。(源點已預流,匯點收集水。) 貳、含水點仍有水。 參、含水點到其鄰點的邊仍有剩餘容量。 肆、鄰點是比含水點低一層的點。
Relabel
給定一個含水點,抬高此含水點。 以下是允許進行Relabel的條件,確定符合後才得進行Relabel: 壹、含水點不是源點和匯點。(請參考Push,沒必要推動就沒必要抬高。) 貳、含水點仍有水。 參、含水點水洩不通。 含水點藉由有剩餘容量的邊,所連到的鄰點,這些鄰點的高度都小於等於含水點。 (當含水點仍找得到低一層的鄰點可以推水過去,就不能抬高。)
演算法
1. 把圖上每個點的高度設為零。 (或者是以匯點作為起點的最短路徑長度作為高度,不影響結果。) 2. 設定起點的高度是V-1(以上),V為圖上點數。 3. preflow。 4. 圖上各點不斷push或relabel,次序隨意,直到無法進行為止。 (或者說,直到圖上除源點匯點以外的所有點都沒水為止。) 5. 匯點所收集的水量,即是最大流的流量。 多餘的水流回源點後,源點所流出的水量,即是最大流的流量。 圖上每條邊的水流,總合起來就是最大流。
經由複雜的推導,總算歸納出單純的演算法──僅以三種「點對鄰點之間」的動作preflow、push、relabel,即可求得最大流。十分精采!
時間複雜度
我們針對preflow、push、relabel的次數下手。
preflow:總共一次,O(V)。
relabel:設定匯點的高度為0,源點的高度為V-1。最差情況下,除源點匯點,最高的點升到了2V-3、最低的點升到了V,流不到匯點的水都回歸匯點了,如下圖所示。利用等差級數梯形公式,得知relabel總共最多O(V²)次。
圖的資料結構為Adjacency Matrix,一次relabel需時O(V),全部的relabel需時O(V³);圖的資料結構為Adjacency Lists,圖上各點各做一次relabel需時O(E),全部的relabel需時O(VE)。
saturating push:對一條邊而言,兩個端點高度逐漸升高,高度範圍為0到2V-3,高度相差一時才能推動,一種高度頂多推動一次,所以一條邊的saturating push總共最多O(V)次。
圖的資料結構為adjacency lists,一次push需時O(1),一條邊的saturating push總共最多O(V)次,圖上總共E條邊,全部的saturating push需時O(VE)。
non-saturating push:同上,一種高度最多推動V次。由於其端點的V個鄰點升高時會補水給端點、其端點最多補水V次。全部的non-saturating push需時O(V²E)。
歸納上述四項,總時間複雜度O(V²E),受限於non-saturating push的次數。
計算最大流的流量
實作時我們建立一個queue來儲存含水點。
Maximum s-t Flow: Discharge
想法
順著高低順序推水是我們的初衷。累積足夠水量後,就慢慢往前推動,不要每次都一口氣推水到最低處,便可以減少push的次數。
Discharge
給定一個含水點,不斷使用Push和Relabel把水排掉,直到沒水。 以下是允許進行Discharge的條件,確定符合後才得進行Discharge: 壹、含水點不是源點和匯點。 貳、含水點仍有水。
演算法
1. preflow。 2. 不斷找符合條件的含水點實施discharge, 直到所有含水點(除源點匯點)都沒水為止。 條件:其他含水點(除源點匯點)的水, 無法沿著目前的容許網路流入此含水點。
【待確認】
時間複雜度
我們針對preflow、push、relabel的次數下手。preflow、relabel、saturating push的時間複雜度都與先前章節相同。此處只分析non-saturating push的時間複雜度。
【待補文字】
由均攤分析可知non-saturating push總共O(V³)次。總時間複雜度O(V³)。
演算法:一直找最高的含水點discharge
(Highest-Label Preflow-Push Algorithm)
1. preflow。 2. 一直找最高的含水點進行discharge(不包括源點匯點), 直到圖上無含水點(不包括源點匯點),
演算法:含水點discharge後,若有升高則挪動順序至首
(Relabel-to-front Algorithm)
1. 建立一個list,裡面包含所有點(但不包括源點匯點)。 註:此list從頭到尾一直都是當下容許網路的拓撲排序。 2. preflow。 3. 按照list順序讀取各點 甲、如果不是含水點,就繼續下一個點, 乙、如果是含水點,就discharge,並且於discharge完之後 a. 如果剛才的discharge有抬高此點(有relabel), 就把此點移到list開頭,並重新由list開頭讀取。 b. 如果剛才的discharge沒有抬高此點(沒有relabel), 就繼續下一個點。
演算法:含水點以FIFO順序discharge
(FIFO Preflow-Push Algorithm)
1. 建立一個queue,裡面只放含水點(但不包括源點匯點),含水點不會重複。 2. preflow,順便把含水點都塞入queue。 3. queue不斷彈出點,進行discharge,直到queue無點。 若discharge時產生了queue裡面沒有的含水點,就塞入queue。
Maximum s-t Flow: Improved Shortest Augmenting Path Algorithm
註記
此演算法沒有廣為人知的正式名稱。
此演算法為Ahuja與Orlin於1991年發表,論文名稱是Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems。該篇論文中同時發表了兩個最大流演算法,因此若直接稱呼Distance-directed Augmenting Path Algorithm,會無法準確指出是哪一個演算法。
Ahuja與Orlin後來出版一本網路流的書籍,書上描述此演算法為「Shortest Augmenting Path Algorithm改良版」,但是仍未給予一個適切的名稱。
演算法
Preflow-Push Algorithm的加強版。以DFS的順序沿著容許邊行走,當遇到死胡同,就relabel,並且回溯,尋找其他可以到達匯點的路徑。
與Preflow-Push Algorithm不同的地方,在於此演算法是找到匯點之後,才沿著擴充路徑來擴充流量,而不是逐點推水。
時間複雜度仍是O(V²E)。
尋找擴充路徑,沿著容許邊行走,從源點走到匯點,途中各點的高度逐次減一。缺一不可。
任何一種高度出現了、又完全消失之後,表示源點到匯點往後無法貫通,開始retreat,可以直接結束演算法。此即cnt的功用。
UVa 10983
演算法
引入阻塞流的概念。以Backtracking的順序而非DFS的順序沿著容許邊行走,尋找擴充流而非擴充路徑。
特色是尋找每一點到匯點的阻塞流(水足夠時)、也就是尋找局部的阻塞流!每次回溯皆實施relabel,隨時調校局部的最短路徑長度!
時間複雜度O(V²E)。
延伸閱讀:height label
有了height label的概念之後,我們可以重新審視之前的擴充路徑演算法,給予更簡潔的解釋。
Augmenting Path Algorithm(Ford-Fulkerson Algorithm) 不使用height label。 隨便找擴充路徑。 Shortest Augmenting Path Algorithm(Edmonds-Karp Algorithm) 每回合都用BFS重新建立height label, 同時用BFS找一條擴充路徑。 Blocking Flow Algorithm(Dinic's Algorithm) 每回合都用BFS重新建立height label, 每回合都用多次DFS找擴充路徑(最後形成阻塞流)。 Improved Shortest Augmenting Path Algorithm 一開始用BFS建立height label(也可以全部設定為零), 每回合都用DFS找擴充路徑。
摘要
最大流問題只有四個要素: 甲、容量(Flow Network)。甲≥0。 乙、流量(Flow)。甲≥乙≥0。 丙、剩餘容量(Residual Network)。甲減乙、反向乙。 丁、遵行方向(Admissible Network)。丁屬於丙:邊兩端高度差為一。 最大流問題: 給定甲暨源點匯點,令乙趨近甲,求乙。 最大流演算法: 以丙的視角看問題,有隙就流。(最大流最小割定理) 以丁的視角看問題,可以縮短流動路線,加速演算法。 最大流演算法有兩大類: 一、擴充路徑法(率先流到匯點) Augmenting Path Algorithm 丙上隨便找一條擴充路徑,不斷找。 (Ford-Fulkerson Algorithm) O(EF) Shortest Augmenting Path Algo. 丙上BFS找一條擴充路徑,最多VE次。 (Edmonds-Karp Algorithm) O(VEE) Blocking Flow Algorithm 丁上找擴充流,最多V次。 (Dinic's Algorithm) O(VVE) Improved Shortest Augmenting 丁上找擴充路徑,最多VE次。 Path Algorithm O(VVE) Capacity Scaling Algorithm 限制甲尺度找擴充流,最多logC次。 O(EElogC) 二、預流推進法(率先流離源點) Preflow-Push Algorithm 隨性推 O(VVE) Relabel-to-front Algorithm 插隊推 O(VVV) FIFO Preflow-Push Algorithm FIFO推 O(VVV) Highest-Label Preflow-Push Algo. 最高推 O(VVV)
Maximum s-t Flow: Orlin's Algorithm
http://jorlin.scripts.mit.edu/Max_flows_in_O(nm)_time.html
目前時間複雜度最低的演算法。使用一些糟糕的手法硬湊出來的,缺乏實務價值。