關于Yuri Boykov and Vladimir Kolmogorov 于2004年提出的max flow / min cut的算法的詳解

這篇文章說的是Yuri Boykov and Vladimir Kolmogorov在2004年提出的一種基于增廣路徑的求解最大流最小割的算法，号稱大部分情況下會很快。而且在算完之後，會自動完成最小割集的構造。

文章參考：《GRAPH BASED ALGORITHMS FOR SCENE RECONSTRUCTION FROM TWO OR MORE VIEWS》這是作者的博士論文，在最後的一章節裡詳細提到了這種算法的思路。

這個算法的思路并不難懂，但是看起來有點難度。文中充滿了q is children of p之類的表述，看着看着就混淆了。而且代碼裡的變量命名也很随意，花了3,4天的時間，終于搞定。

算法的直覺了解

第一個改進：

首先算法采用了兩條增廣路徑，分别從source和sink出發，邊搜尋邊标号，這樣當所有的點都被搜尋并标号後，最小割集也就形成了。

所有在最前沿的點稱為active node，這些點的任務是去發展新的node。而被active node包圍起來的那些點，則稱之為passive node。

而沒有被發掘出來的點則稱之為free node。

第二個改進：

基于增廣路徑的算法都是遵循：找出一個可行流----》更新殘留網絡----》然後再找下一個可行流。

此算法需要不斷地去找可行流，而每次找都得從源點重新開始進行一個廣度周遊或者深度周遊直到找到彙點。這篇文章的算法正是基于此來進行改進。

找到一個可行流後，要進行augmention，然後必然會出現飽和的邊，比如這樣的一條路中：p1----->p2---->p3----->p4，p2->p3這條邊飽和了。如果我們不管他，還是繼續周遊去尋找彙點，那麼當你再次找到一條路後，那麼這條路中就有可能包含一些已經飽和路徑，那就沒法進行增廣了。是以，我們必須要去調整那些飽和的邊，使得在已經建構的路徑中不存在飽和的邊。在本例中，p3稱之為orphan（孤點），那麼接下來就得做一個adopt orphan的操作，呵呵，名字起得很有意思（養育孤兒），意思就是說給每個p3這樣的孤兒點找一個新的parent，養育完就沒有orphan存在了。方法如下：

檢查p3的neighbors，看看有沒有一個neighbor, let's say node q，s.t.

(1). q->p3滿足容量大于0

(2). q是已經被搜過的點，也就是說q已經在我們的span tree了，in another word，當我們沿着彙點逆流而上搜尋到q時，可以順利地找到q的father，進而最終可以順藤摸瓜摸到source上。

(3). 通過q最終能到達source或者sink這樣的終點。這是因為有可能順着q走着走着，最終走到一個free node去了。或者走到一個orphan去了，而這個orphan最終也無人撫養而變成free node。

那麼如果找不到這樣的q，那麼p3就不得不變成free node。然後再做以下兩個調整：

(4). 對于p3的鄰居pk，如果pk到p3的邊(pk-->p3)的容量大于0, 則将pk設為active。

(5). 對于p3的鄰居ph，如果p3=parent(ph)，那麼把ph也設定為orphan，加入到orphan集合裡。

這是因為當有一條路從sink走到ph的時候，會發現無路可走了，因為parent(ph)是一個free node!

是以我們必須對ph也做相同的處理，要麼找一個新的parent，要麼您老人家變成free node，先一邊涼快會！

orphan集合中在增廣時建立，每次更新一個邊後，如果發現改變後的邊的殘留流量=0，則把邊指向的那個點加入orphan set。

在adoption階段，反複從orphan set中取點，每取出一個孤兒，首先看看能不能找到一個新的parent，如果找不到則令其變成free node，并把他的child變成orphan，加入到orphan集合中。循環往複，直到orphan set = 空集。

細節：

對上述的(3)可以進行優化。

優化一：不必每次要追溯到source/sink才罷休。

因為對于orphan的每一個鄰居進行判斷其是否originate from TERMINATE node時，都要逆流追溯至source / sink點。那麼其中的一些點可能要被追溯多次，那麼這是一個重複的操作。如果一個點，已經被證明了，他是可以到達source / sink的，那麼下次當有點經過他的時候，他就可以直接告訴該點，OK，哥們歇歇吧，你是valid的，通過我可以追溯到source/sink。這就是在algorithm tunning裡提到的mark的意思。

優化二：選擇離source/sink最近的那個neighbor，作為orphan的新parent.

要實作這個優化，必須給每個節點附加一個屬性：該節點到source/sink的最短距離。

并且在growth階段，當一個active node q1 遇到另一個active node q2時，要比較一下是否把parent(q2)=q1後，q2到source/sink的距離更短，如果是，那麼就調整下q2，使得它變成q1的child。正所謂：

人往高處走，水往低處流，節點都往終點湊！