feasible s-t flow
容量下限(流量下限)
先前只討論容量上限,並未討論容量下限。
然而,容量下限有個問題。舉例來說,當容量下限形成環,從源點流出一單位水流,即可滿足容量下限:流往環,不斷繞環,原路返回。導致「憑空出現循環水流」的弔詭現象。
大家目前沒有任何對策!因此轉為討論「循環流」:去掉源點匯點,允許憑空出現循環水流。請見後面章節「 flow 」。
feasible s-t flow ( s-t flow )
「可行流」是符合容量限制的流。「可行流」與「流」的定義完全一樣,我們常常省略「可行」兩個字。差別在於多了「可行」之後,我們專注於「找到一個流」,而非「流量是多少」。
想要形成可行流,每條邊、每個點、每個割的流量,必須符合容量限制:
一、邊:流量,大於等於容量下限,小於等於容量上限。 二、點:入流量,大於等於出容量下限,小於等於出容量上限。 出流量,大於等於入容量下限,小於等於入容量上限。 三、割:同上。
可行流目前沒有演算法。無法處理「憑空出現循環水流」。
maximum s-t flow / minimum s-t flow
有了容量下限,除了討論「最大流」,還可以討論「最小流」。
目前沒有演算法。無法處理「憑空出現循環水流」。
minimum cost maximum s-t flow
minimum cost maximum s-t flow:
cycle canceling algorithm
演算法
圖上不可有負成本環,避免「憑空出現循環水流」。
一、先找一個最大流。 二、在剩餘圖上,不斷找負成本環,建立迴流降低成本。 直到找不到負成本環為止,即是最小成本最大流。
在一個最大流當中,建立一條封閉的迴流,不會影響總流量,也不會違反流量守恆的規則,雖然會浪費容量空間,但是有機會減少總成本。事實上可以證明,剩餘圖沒有負成本環,即是最小成本最大流,證明省略。
尋找負成本環
有三種方式!
負環:運用 Moore's algorithm 。整個演算法過程中,最多出現 C 個負成本環, C 是最大的管線容量上限;時間複雜度 O(VEC) ,偽多項式時間。
最小環:照理說是最理想的方式,可以較快達到最小成本最大流。然而,求最小環是 NP-complete 問題,時間複雜度是指數時間。
最小平均數環:意外的是個不錯的選擇。整個演算法過程中,最多出現 O(VE²logV) 個最小平均數環;時間複雜度 O(V²E³logV) ,多項式時間。證明省略。
minimum cost maximum s-t flow:
successive shortest path algorithm
演算法
圖上不可有負成本環,避免「憑空出現循環水流」。
仿照 Ford–Fulkerson algorithm ,不斷尋找成本最小的擴充路徑。證明省略。
一開始沒有負成本環,往後就沒有負成本環。
一、一開始的剩餘圖沒有負成本環。
二、成本最小的擴充路徑,擴充之後讓剩餘圖增加了逆向邊(成本隨之變號,增加了負成本邊),但是剩餘圖仍舊沒有負成本環。證明省略。
如此一來,可以確保剩餘圖隨時都能實施最短路徑演算法。
尋找成本最小的擴充路徑
溯洄沖減後,剩餘圖多出許多逆向的負成本邊,因此必須採用允許負邊的最短路徑演算法,例如 Moore's algorithm 、 Floyd–Warshall algorithm 。
或者利用 Johnson's algorithm 的調整權重手法,將負邊調整為非負邊。此時成本最小的擴充路徑就會變成零成本邊,擴充之後的剩餘圖,就不會多出逆向的負成本邊,而是多出逆向的零成本邊!如此一來,就可採用不允許負邊的最短路徑演算法,例如 Dijkstra's algorithm ,降低時間複雜度。
一開始圖上可能有負成本邊,預先實施一次 Moore's algorithm 調整權重,往後就可持續使用 Dijkstra's algorithm 了。每次實施 Dijkstra's algorithm 之後,就馬上調整權重。
一、用Moore's algorithm調整權重,讓每條邊的成本為非負值。 二、不斷尋找成本最小的擴充路徑,直到找不到為止: 甲、用Dijkstra's algorithm尋找成本最小的擴充路徑。 乙、調整權重,讓每條邊的成本為非負值。 丙、擴充流量。
找一條擴充路徑需時 O(V²) ,最多找 O(F) 條,時間複雜度 O(V²F) ,偽多項式時間。
找出一個最小成本最大流+流量+成本
minimum cost maximum s-t flow:
primal–dual algorithm
演算法
圖上不可有負成本環,避免「憑空出現循環水流」。
仿照 blocking flow algorithm ,每回合找到全部的成本最小的擴充路徑。
利用最短路徑長度,調整圖上所有邊的權重成為非負數之後,此時最短路徑上的邊就是零成本邊。在零成本邊所構成的圖當中,找最大流,便可以一次找到全部的成本最小的擴充路徑。
時間複雜度我也不知道。
flow
註記
flow 與 s-t flow 是兩個不同的概念。然而古代人當初定義問題時,卻將兩者都稱作 flow ,從此之後便混淆不清了。
cut 與 s-t cut 亦有類似情況。古代人當初沒有 cut 的概念,將 s-t cut 直接稱作 cut 。不過自從有人發表 cut 的演算法之後,眾人便開始注重用詞了。
以下章節, flow 譯作「流」或「循環流」, s-t flow 譯作「源匯流」。
flow
從現在起,水流不再從源點流到匯點,水流改為不斷循環。
要計算總流量,可將水流分解成數個環,以環流量的總和作為總流量。每次挑一條有水流的邊開始尋找環,最多分解成 E 個環。
supply / demand
「供點」有水注入、「需點」有水洩出,彷彿源點與匯點。圖上可以有多個供點與需點,供水量總和必須等於需水量總和,才有機會形成可行流。
圖上每一點皆有供需水量: supply 的供需水量為正值,該點流出多於流入; demand 的供需水量為負值,該點流入多於流出;其他的點的供需水量為零,流入等於流出。
供需水量 = 流出水量 - 流入水量
導入 supply 與 demand 之後,總流量的定義就不明確了。這裡姑且定義成: supply 的總和,再加上不受 supply 與 demand 影響的循環流流量。
最大流最小割定理、可行流定理
導入水流流量:任意一個割,甲側流往乙側的水量總和,等於乙側流往甲側的水量總和。
導入容量上限:任意一個割,甲側流往乙側的水量總和,小於等於甲側到乙側的容量總和。最大流流量,小於等於任何一個「管線容量的最小 s-t 割」!
導入供需水量:任意一個割,甲側的供需水量總和,必須小於等於甲側到乙側的容量總和,才能形成可行流。
導入容量下限:任意一個割,甲側到乙側的容量下限總和,必須小於等於甲側到乙側的容量上限總和、也要小於等於乙側到甲側的容量上限總和,才能形成可行流。
容量下限變成零
有向邊的容量下限,得移轉至 supply 與 demand 。
預先流水,水量等於容量下限:
必須記錄每條邊的預流水量與耗費成本,以利之後還原。
容量上限變成無限大
其實沒有必要移除容量上限 ── 最大流演算法皆支援容量上限。不過還是介紹一下吧。
移除容量下限後,可以進一步移除容量上限。容量上限添加至終點,然後回沖:
移除容量上限後,變成二分圖,得以設計更簡潔的資料結構與演算法。
負成本變成正成本
運用溯洄沖減,可以把負成本變成正成本。
預先流水,水量等於容量上限:
必須記錄每條邊的預流水量和耗費成本,以利之後還原。
無向邊變成有向邊
無向邊得同時雙向流動。一條無向邊可以改為兩條方向相反的有向邊,可是必須共用容量上下限。
成本非負、沒有容量下限:為了降低成本,來回水流可以變成單向水流。上述兩條方向相反的有向邊,大可不必共用容量上限,宛如普通的有向邊。
成本非負、擁有容量下限:預先在無向邊上來回流動,滿足容量下限。流量是容量下限的一半,可以是 0.5 。如果流量只能是整數,則可以類比為 0/1 knapsack problem ,屬於 NP-complete 問題。
成本為負:同上。流量是實數,就來回流動。流量是整數, NP-complete 。
歸約
feasible s-t flow -> feasible flow -> maximum s-t flow 導入成本,依然如此。
可行源匯流化作可行循環流。匯點到源點增加一條管線,容量上限無限大(圖上所有邊的容量上限總和),成本無限小。
可行循環流化作最大源匯流。新增源點與匯點,源點接至 supply ,容量上限為供水量; demand 接至匯點,容量上限為需水量。然後嘗試求最大源匯流,若源點管線與匯點管線皆滿溢,則有可行循環流,反之則無。拆除新增管線,最大源匯流就變成可行循環流。
總結
流的問題總是可以簡化成:有容量上限、無容量下限、成本非負、有向邊,許多 supply 和 demand 。
無論流動方式是循環流、源匯流,無論最佳化目標是最大流、最小流、可行流,都可以歸約成 minimum cost maximum s-t flow 。
UVa 11647 1259 ICPC 3787 4722 5131
feasible flow
「可行流」。符合供需水量、容量上下限的流。
直覺的方式,就是歸約。進階的方式,就是瞭解歸約過程之後,直接以原圖實施計算,不歸約、不改圖。
承襲 maximum s-t flow 演算法,額外考慮 flow 、 supply 、 demand 等新概念。
不斷尋找起點為 supply 、終點為 demand 的擴充路徑,進行擴充後就根據水量減損 supply 、增益 demand ,直到圖上沒有 supply 與 demand 為止。
maximum flow
「最大流」。流量最大的可行流。
一、首先隨便找出一個可行流,然後不斷找擴充環。
根據最大流最小割定理,剩餘圖沒有擴充環,即是最大流。
二、窮舉所有兩點之間容量 s-t 割,取最小值。【尚待確認】
minimum flow
「最小流」。流量最小的可行流。
一、擴充路徑堅持使用點互斥路徑,即得最小流。【尚待確認】
二、首先隨便找出一個可行流,然後不斷消去擴充環。【尚待確認】
我找不到任何有關最小流的正確性證明!
minimum cost flow
「最小成本流」。成本最小的可行流。
承襲 minimum cost maximum s-t flow 演算法。
cycle canceling algorithm :先找到任意一個可行流,再以負成本環進行擴充。
successive shortest path algorithm 與 primal–dual algorithm :不斷尋找起點為 excess 、終點為 deflict 、成本最小的擴充路徑,直到所有 excess 與 deflict 成為零。如果 excess 與 deflict 沒有同時成為零,則沒有可行流。
excess / deficit
「積水點」水量超出平衡,「缺水點」水量低於平衡。當圖上有 excess 與 deficit ,表示流量不平衡,不是可行流。
積缺水量 = 流入水量 - 流出水量 + 供需水量
multi-commodity flow
k vertex-disjoint paths
k edge-disjoint paths
給定 k 組起點與終點,找齊 k 條路徑,點(邊)皆相異;除了起點與終點。可能找不到。
flow 問題,源點與匯點不必對應, P 問題。
此問題,起點與終點必須對應, NP-complete 問題。
差別在於交叉路徑。 flow 問題,運用溯洄沖減,交叉路徑總是變成不交叉路徑。此問題則不然。
UVa 11301
k vertex-disjoint s-t paths
k edge-disjoint s-t paths
給定一組起點與終點,找出 k 條路徑,點(邊)皆相異;除了起點與終點。起點都是同一點、終點都是同一點,無所謂對不對應。可能找不到。
解法是 maximum s-t flow 。
進階版本,這 k 條路徑的權重總和必須最小。
解法是 minimum cost maximum s-t flow 。
multi-commodity flow
指定多組供點、需點,必須對應。
流量是實數, P 問題。流量是整數, NP-complete 問題,大家改為研究速度飛快的近似演算法。