網(wǎng)絡(luò)流的增廣路算法和預(yù)流推進算法

網(wǎng)絡(luò)流的增廣路算法和預(yù)流推進算法第一頁，共九十二頁，編輯于2023年，星期三一些符號和定義V表示整個圖中的所有結(jié)點的集合.E表示整個圖中所有邊的集合.G=(V,E),表示整個圖.s表示網(wǎng)絡(luò)的源點,t表示網(wǎng)絡(luò)的匯點.對于每條邊(u,v),有一個容量c(u,v)(c(u,v)>=0)如果c(u,v)=0，則表示(u,v)不存在在網(wǎng)絡(luò)中。如果原網(wǎng)絡(luò)中不存在邊(u,v)，則令c(u,v)=0對于每條邊(u,v),有一個流量f(u,v).第二頁，共九十二頁，編輯于2023年，星期三v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)一個簡單的例子.網(wǎng)絡(luò)可以被想象成一些輸水的管道.括號內(nèi)右邊的數(shù)字表示管道的容量,左邊的數(shù)字表示這條管道的當(dāng)前流量.第三頁，共九十二頁，編輯于2023年，星期三網(wǎng)絡(luò)流的三個性質(zhì)1、容量限制:f[u,v]<=c[u,v]2、反對稱性：f[u,v]=-f[v,u]3、流量平衡:對于不是源點也不是匯點的任意結(jié)點,流入該結(jié)點的流量和等于流出該結(jié)點的流量和。結(jié)合反對稱性,流量平衡也可以寫成:

只要滿足這三個性質(zhì),就是一個合法的網(wǎng)絡(luò)流.第四頁，共九十二頁，編輯于2023年，星期三最大流問題定義一個網(wǎng)絡(luò)的流量（記為|f|）=最大流問題，就是求在滿足網(wǎng)絡(luò)流性質(zhì)的情況下，|f|的最大值。第五頁，共九十二頁，編輯于2023年，星期三殘量網(wǎng)絡(luò)為了更方便算法的實現(xiàn)，一般根據(jù)原網(wǎng)絡(luò)定義一個殘量網(wǎng)絡(luò)。其中r(u,v)為殘量網(wǎng)絡(luò)的容量。r(u,v)=c(u,v)–f(u,v)通俗地講：就是對于某一條邊（也稱弧），還能再有多少流量經(jīng)過。Gf殘量網(wǎng)絡(luò),Ef表示殘量網(wǎng)絡(luò)的邊集.第六頁，共九十二頁，編輯于2023年，星期三例1v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)v1tsv2232422原網(wǎng)絡(luò)(a,b)表示(流量f,容量c)殘量網(wǎng)絡(luò)（如果網(wǎng)絡(luò)中一條邊的容量為0,則認為這條邊不在殘量網(wǎng)絡(luò)中。r(s,v1)=0,所以就不畫出來了。另外舉個例子：r(v1,s)=c(v1,s)–f(v1,s)=0–(-f(s,v1))=f(s,v1)=4.圖1圖2第七頁，共九十二頁，編輯于2023年，星期三例1從殘量網(wǎng)絡(luò)中可以清楚地看到：因為存在邊(s,v2)=3,我們知道從S到v2還可以再增加2單位的流量；因為存在邊(v1,t)=2,我們知道從v1到t還可以再增加2單位的流量。v1tsv2232422第八頁，共九十二頁，編輯于2023年，星期三后向弧其中像(v1,s)這樣的邊稱為后向弧,它表示從v1到s還可以增加4單位的流量。但是從v1到s不是和原網(wǎng)絡(luò)中的弧的方向相反嗎？顯然“從v1到s還可以增加4單位流量”這條信息毫無意義。那么，有必要建立這些后向弧嗎？v1tsv2232422第九頁，共九十二頁，編輯于2023年，星期三為什么要建立后向弧顯然，例1中的畫出來的不是一個最大流。但是，如果我們把s->v2->v1->t這條路徑經(jīng)過的弧的流量都增加2,就得到了該網(wǎng)絡(luò)的最大流。注意到這條路徑經(jīng)過了一條后向弧:(v2,v1)。如果不設(shè)立后向弧，算法就不能發(fā)現(xiàn)這條路徑。從本質(zhì)上說，后向弧為算法糾正自己所犯的錯誤提供了可能性，它允許算法取消先前的錯誤的行為（讓2單位的流從v1流到v2)第十頁，共九十二頁，編輯于2023年，星期三為什么要建立后向弧當(dāng)然,可以把上面說的情況當(dāng)成特殊情況來處理。但使用后向弧可以使編程簡單許多.注意,后向弧只是概念上的,在程序中后向弧與前向弧并無區(qū)別.第十一頁，共九十二頁，編輯于2023年，星期三增廣路增廣路定義：在殘量網(wǎng)絡(luò)中的一條從s通往t的路徑，其中任意一條弧(u,v)，都有r[u,v]>0。綠色的即為一條增廣路。v1tsv2232422第十二頁，共九十二頁，編輯于2023年，星期三增廣路算法增廣路算法：每次用BFS找一條最短的增廣路徑，然后沿著這條路徑修改流量值（實際修改的是殘量網(wǎng)絡(luò)的邊權(quán)）。當(dāng)沒有增廣路時，算法停止，此時的流就是最大流。下面證明增廣路算法的正確性.第十三頁，共九十二頁，編輯于2023年，星期三將f,c,r的定義域擴展為點集(在以后的敘述中,大寫字母X,Y,S,T一般均表示點集)點集間的流量和:f(X,Y)=即:X中的任意一點與Y中的任意一點組成的所有邊上的流量之和.(邊的方向為從X中的結(jié)點到Y(jié)中的結(jié)點)c,r等函數(shù)都有類似的定義.(點集間的容量和、點集間的殘量網(wǎng)絡(luò)容量和)第十四頁，共九十二頁，編輯于2023年，星期三結(jié)論11.f(X,X)=0 (由流量反對稱性)2.f(X,Y)=-f(Y,X) (有流量反對稱性)3.f(X∪Y,Z)=f(X,Z)+f(Y,Z)(顯然)4.f(X,Y∪Z)=f(X,Y)+f(X,Z)(顯然)第十五頁，共九十二頁，編輯于2023年，星期三最大流最小割定理網(wǎng)絡(luò)流中這三個條件等價（在同一個時刻）:1、f是最大流2、殘量網(wǎng)絡(luò)中找不到增廣路徑3、|f|=c(S,T)第十六頁，共九十二頁，編輯于2023年，星期三

1、f是最大流

2、殘量網(wǎng)絡(luò)中找不到增廣路徑

3、|f|=c(S,T)

1->2證明:顯然.假設(shè)有增廣路徑,由于增廣路徑的容量至少為1,所以用這個增廣路徑增廣過后的流的流量肯定要比f的大,這與f是最大流矛盾.第十七頁，共九十二頁，編輯于2023年，星期三割的定義一個割(S,T)由兩個點集S,T組成.S+T=Vs屬于S.t屬于T.提出割的定義,是為后面的證明作鋪墊.第十八頁，共九十二頁，編輯于2023年，星期三結(jié)論2(點集總流量為零)不包含s和t的點集,于它相關(guān)聯(lián)的邊上的流量之和為0.證明:f(X,V)==(由流量平衡)=0第十九頁，共九十二頁，編輯于2023年，星期三結(jié)論3任意割的流量等于整個網(wǎng)絡(luò)的流量.證明:f(S,T)=f(S,V)–f(S,S)(由輔助定理1)=f(S,V) (由輔助定理1)=f(S,V)+f(S–s,V)(同上)=f(s,V)(由輔助定理2)=|f| (由|f|的定義)第二十頁，共九十二頁，編輯于2023年，星期三結(jié)論4網(wǎng)絡(luò)的流量小于等于任意一個割的容量.(注意這個與輔助定理3的區(qū)別.這里是容量)即|f|<=c(S,T)證明:|f|=f(S,T)=(由定義)<=(由流量限制)=c(S,T)第二十一頁，共九十二頁，編輯于2023年，星期三2->3證明:定義S=s∪{v|在殘量網(wǎng)絡(luò)中s到v有一條路徑};T=V-S.則(S,T)是一個割.|f|=f(S,T)(由輔助定理3)而且,r(S,T)=0.假設(shè)不為0,則在殘量網(wǎng)絡(luò)中,兩個集合間必定有邊相連,設(shè)在S的一端為v,在T的一端為u.那么,s就可以通過v到達u,那么根據(jù)S的定義,u就應(yīng)該在S中.矛盾.所以,|f|=f(S,T)=c(S,T)–r(S,T)=c(S,T)

1、f是最大流

2、殘量網(wǎng)絡(luò)中找不到增廣路徑

3、|f|=c(S,T)

第二十二頁，共九十二頁，編輯于2023年，星期三3->1證明:|f|<=c(S,T)(輔助定理4)因為我們已經(jīng)有|f|=c(S,T),如果最大流的流量是|f|+d(d>0),那么|f|+d肯定不能滿足上面的條件.

1、f是最大流

2、殘量網(wǎng)絡(luò)中找不到增廣路徑

3、|f|=c(S,T)

第二十三頁，共九十二頁，編輯于2023年，星期三增廣路算法的正確性如果最大流最小割定理不能從2推出3,那么存在這樣一種可能性:盡管找不到增廣路徑了,但由于前面的錯誤決策,導(dǎo)致f還沒有到達最大流,卻不能通過修改當(dāng)前流來得到最大流.但由于最大流最小割定理的三個條件互相等價(1->2,2->3,3->1),一個流是最大流當(dāng)且僅當(dāng)它沒有增廣路徑.第二十四頁，共九十二頁，編輯于2023年，星期三增廣路算法的效率設(shè)n=|V|,m=|E|每次增廣都是一次BFS,效率為O(m)所以,總共的時間復(fù)雜度為O(m*f*)其中f*為增廣次數(shù).怎么求f*?第二十五頁，共九十二頁，編輯于2023年，星期三f*對于隨機數(shù)據(jù),f*的值與n比較接近.當(dāng)m不太大也不太小時,f*的值較大.(我出隨機數(shù)據(jù)的方法是:固定地為源點和匯點連上一些邊,然后隨機生成中間的邊.中間的邊保證邊的兩個端點的編號相差不太大.這與不少題目轉(zhuǎn)成網(wǎng)絡(luò)流后形成的圖相似)第二十六頁，共九十二頁，編輯于2023年，星期三f*的理論上界考慮每一次增廣,至少有一條邊的r(u,v)值等于增廣路徑的流量.稱這些邊為臨界邊.增廣之后,這條臨界邊就在殘量網(wǎng)絡(luò)中消失.假設(shè)一條臨界邊對應(yīng)一次增廣(事實上很難達到這樣),令每條邊成為臨界邊的次數(shù)為k(u,v),則有f*=O(m*k).k的上界?第二十七頁，共九十二頁，編輯于2023年，星期三k的上界如果要讓一條曾經(jīng)的臨界邊(u,v)再次成為臨界邊,則必須有一條增廣路徑包含邊(v,u).因為每次增廣之后臨界邊就消失,要讓他再次成為臨界邊至少要讓他再次在殘量網(wǎng)絡(luò)中出現(xiàn),即(v,u)要被增廣.結(jié)合上面的結(jié)論可以證明,當(dāng)算法取的增廣路總是殘量網(wǎng)絡(luò)中的最短路,任意一條邊成為臨界邊的次數(shù)至多為n/2-1.因此,增廣路算法的效率為O(f*m)=O(km^2)=O(nm^2).(這只是個上界,一般情況是達不到的)備注中為增廣路算法我的代碼實現(xiàn)。數(shù)組u是殘量網(wǎng)絡(luò)的容量。第二十八頁，共九十二頁，編輯于2023年，星期三預(yù)流推進算法下面將介紹一個更直觀且時間效率更優(yōu)的算法.第二十九頁，共九十二頁，編輯于2023年，星期三一個直觀的想法如果給你一個網(wǎng)絡(luò)流,讓你手算出它的最大流,你會怎么算?一般人都會嘗試著從源點出發(fā),讓每條邊的流量盡可能得大,然后一點點往匯點推,直到遇到一條比較窄的弧,原先的流量過不去了,這才減少原先的流量.第三十頁，共九十二頁，編輯于2023年，星期三v1tsv2(0,2)(4,4)(0,4)(3,3)(0,2)例2.一個直觀的想法大致的思路：從源點出發(fā)，逐步推進。稱當(dāng)前狀態(tài)下不滿足流量平衡的結(jié)點為“溢出的結(jié)點”.(對于結(jié)點u,f(V,u)>0)令e(u)=f(V,u),稱為u點的贏余，直觀地描述，就是“流入的比流出的多多少”。e(v1)=4,e(v2)=3。不斷將溢出的結(jié)點中的贏余往后繼點推進,直到贏余都聚集在t.第三十一頁，共九十二頁，編輯于2023年，星期三v1tsv2(2,2)(4,4)(0,4)(3,3)(2,2)如果多推了一些流量,我們可以再把它推回來.(如e(v2)=3,但這3個單位的贏余已經(jīng)沒地方去了,只能推回來.)(沿著后向弧)這副圖是原網(wǎng)絡(luò)而不是殘量網(wǎng)絡(luò),因此沒把后項弧畫出來)例2.一個直觀的想法第三十二頁，共九十二頁，編輯于2023年，星期三v1tsv2(2,2)(4,4)(0,4)(3,3)(2,2)程序沒有全局觀?!此時e(v2)=3.正確的回推法是往(v2,s)推1,往(v2,v1)推2,然后使得這2個單位的贏余可以從(v1,t)推到t上。但程序沒有全局觀,它萬一往(v2,s)推了3個單位怎么辦?我們總不能嘗試所有的可能性吧,那樣就變成搜索了.第三十三頁，共九十二頁，編輯于2023年，星期三引導(dǎo)機制把流推錯可能導(dǎo)致產(chǎn)生的流不是最大流.我們需要有一個能引導(dǎo)流的推進方向的機制,當(dāng)它發(fā)現(xiàn)我們先前的推進是錯誤的時候,能沿著正確的后向弧回推回來.由于建立了后向弧,正推與回推在程序中并無卻別，都是在推殘量網(wǎng)絡(luò)中的一條邊.第三十四頁，共九十二頁，編輯于2023年，星期三高度標(biāo)號的引導(dǎo)作用高度標(biāo)號就是這樣的一個引導(dǎo)機制.我們規(guī)定,如果一個結(jié)點溢出了,那么他的多余的流量只能流向高度標(biāo)號比自己低的結(jié)點.(“水往低處流”)當(dāng)然,高度標(biāo)號不可能事先知道往哪些方向推才是正確的.它將按情況動態(tài)改變自己的值,從而正確地引導(dǎo)流向.第三十五頁，共九十二頁，編輯于2023年，星期三重標(biāo)號操作當(dāng)一個結(jié)點有贏余(溢出了),周圍卻沒有高度比它低的結(jié)點時候,我們就用重標(biāo)號操作使它的標(biāo)號上升到比周圍最低的結(jié)點略高一點,使他的贏余能流出去.贏余千萬不能困在某個結(jié)點里.對于任意一個非源非匯的結(jié)點，有贏余就意味著它不滿足流量平衡，也就意味著整個網(wǎng)絡(luò)流不是一個真正合法的網(wǎng)絡(luò)流。第三十六頁，共九十二頁，編輯于2023年，星期三重標(biāo)號操作對于例2的這種情況,v2中過多的贏余最終會沿著(v2,v1)、(v2,s)流回去(雖然他們一開始流錯了方向,但后來又被回推,等于說是被改正了)。只有當(dāng)非源非匯的結(jié)點中的贏余全部流到匯點或流回源點后，這個流才重新合法。第三十七頁，共九十二頁，編輯于2023年，星期三高度函數(shù)高度函數(shù)h(v)返回一個v的高度標(biāo)號。高度函數(shù)有三個基本條件：h(s)=|V|h(t)=0對于Ef(殘量網(wǎng)絡(luò))中的每一條邊(u,v),(r(u,v)>0) h(u)<=h(v)+1這第三個條件看上去有些奇怪.既然r(u,v)>0,那就表示從u到v還可以增加流量,那h(u)就應(yīng)該比h(v)高才對.的確,我們后面還將規(guī)定,只有在h(u)>h(v)的時候才能應(yīng)用推進操作(將一個結(jié)點的盈余推進到另一個結(jié)點的操作).而高度函數(shù)為了滿足其合法性,還要滿足上述的這三個條件.后面我們將利用這三個條件證明預(yù)流推進算法的正確性。第三十八頁，共九十二頁，編輯于2023年，星期三高度函數(shù)的條件的實質(zhì)h(u)<=h(v)+1.這個條件實質(zhì)上是要求高度不能下降的太快，即水只能在高度相差不多的地方緩緩流過，不能像瀑布一樣從很高的地方流到很低的地方。(否則就有流錯的危險)這和A*算法中的啟發(fā)函數(shù)必須“相容”的條件類似。h函數(shù)的緩慢下降，保證了算法的正確性。后面我們將看到這個條件的作用.第三十九頁，共九十二頁，編輯于2023年，星期三兩個關(guān)鍵操作推進操作(將一個結(jié)點的盈余推到另一個結(jié)點)重標(biāo)號操作(更改一個結(jié)點的高度值,使其的盈余能朝著更多的地方流動)第四十頁，共九十二頁，編輯于2023年，星期三推進操作使用對象：一條邊(u,v)使用條件：e(u)>0，r(u,v)>0,h(u)=h(v)+1（u溢出，(u,v)在殘量網(wǎng)絡(luò)中，兩者的高度差為1）推進量為e(u)與r(u,v)的最小值。推進時同時更改相關(guān)的r與e的值。第四十一頁，共九十二頁，編輯于2023年，星期三推進操作偽代碼ProcedurePush(u,v)Xmin{e(u),r(u,v)}Dec(r(u,v),x) Inc(r(v,u),x)Dec(e(u),x)Inc(e(v),x)第四十二頁，共九十二頁，編輯于2023年，星期三重標(biāo)號操作使用對象：一個結(jié)點u使用條件：結(jié)點u溢出；殘量網(wǎng)絡(luò)中周圍所有的點的高度都不比它低。Relabel(u)u(u)=min{h(v)|(u,v)是殘量網(wǎng)絡(luò)總的邊}+1使用了重標(biāo)號操作后,至少存在一個(u,v)滿足h(u)=h(v)+1.第四十三頁，共九十二頁，編輯于2023年，星期三預(yù)流初始化(Init-Preflow)一開始的時候，我們要讓和源點s相關(guān)連的邊都盡可能的充滿。但由于s沒有溢出，不符合推進操作的使用條件，我們需要另寫一段初始化的代碼。還得做的一件事是初始化高度函數(shù).h(s)=nh(v)=0(v<>s)對于所有與s相關(guān)聯(lián)的點v，Inc(e(v),c(s,v)),Dec(e(s),c(s,v))將邊(s,v)反向，變成(v,s)（在殘量網(wǎng)絡(luò)中）。初始化過后，e(s)變成負數(shù)。第四十四頁，共九十二頁，編輯于2023年，星期三結(jié)論5對于一個溢出的結(jié)點，兩個關(guān)鍵操作（推進和重標(biāo)號）能且只能應(yīng)用一個。證明：對于一個溢出的結(jié)點u,和所有與他相關(guān)聯(lián)的點v((u,v)在殘量網(wǎng)絡(luò)中存在),必然有h(u)<=h(v)+1.(由高度函數(shù)的定義).根據(jù)v分成兩種情況:1).所有v都有h(u)<h(v)+12).至少存在一個v,使得h(u)=h(v)+1.而1)2)互為否命題,不能同時成立或同時不成立.那么1)對應(yīng)重標(biāo)號,2)對應(yīng)推進,兩者必能應(yīng)用一個且只能應(yīng)用一個.第四十五頁，共九十二頁，編輯于2023年，星期三一般的預(yù)流推進算法由輔助定理5,得到了一個一般的預(yù)流推進算法.(好短)Init-PreflowWhile存在一個溢出的結(jié)點選一個結(jié)點,應(yīng)用相應(yīng)的關(guān)鍵操作(推進或重標(biāo)號).當(dāng)不存在溢出結(jié)點時(s,t不算),算法結(jié)束,得到一個可行流,并且還是最大流.第四十六頁，共九十二頁，編輯于2023年，星期三預(yù)流推進算法的正確性預(yù)流只是不滿足流量平衡,網(wǎng)絡(luò)流的前兩條性質(zhì)---容量限制和反對稱性它還是滿足的.當(dāng)不存在溢出結(jié)點時,流量平衡也滿足了.所以,當(dāng)算法結(jié)束時,我們得到一個可行流(合法流).為什么他是一個最大流呢?下面先看幾個結(jié)論:第四十七頁，共九十二頁，編輯于2023年，星期三結(jié)論6(結(jié)點高度永不下降)只有重標(biāo)號操作能更改結(jié)點的高度標(biāo)號.在重標(biāo)號操作應(yīng)用前,必有h(u)<=h(v)(u,v相鄰).令v0=h值最小的一個v,則h(u)=h(v0)+1>=h(u)+1.所以,在重標(biāo)號操作后,高度標(biāo)號至少+1.第四十八頁，共九十二頁，編輯于2023年，星期三結(jié)論7在算法執(zhí)行過程中,h始終是一個合法的高度函數(shù).(滿足那三個條件)1).考察一個被重標(biāo)號的結(jié)點u.設(shè)(u,v)存在于Ef,v0是所有v中h最小的一個.H’(u)=h(v0)+1,滿足h(u)’<=h(v0)+1,而h(v0)<=h(v),所以h’(u)<=h(v)+1.設(shè)(w,u)存在于Ef,則h(w)<=h(u)+1<=h’(u)+1.仍舊滿足.第四十九頁，共九十二頁，編輯于2023年，星期三結(jié)論7在算法執(zhí)行過程中,h始終是一個合法的高度函數(shù).(滿足那三個條件)2).考察一個被推進的邊(u,v).(v,u)可能是在這次推進之后才出現(xiàn)在Ef中.它的出現(xiàn)使得新增了一個限制條件:h(v)<=h(u)+1.不過,這顯然是滿足的,因為推進操作的使用條件是h(u)=h(v)+1.那么h(v)=h(u)-1<=h(u)+1第五十頁，共九十二頁，編輯于2023年，星期三結(jié)論8(預(yù)流中無增廣路)當(dāng)h是一個合法的高度函數(shù)時,Gf中始終不存在增廣路.(這個定理展示了h的條件的重要性和巧妙性)證明:假設(shè)存在增廣路p=(v0,v1,…vk),其中v0=s,vk=t.因為增廣路徑中無重復(fù)點,k+1<=|V|,即k<|V|.第五十一頁，共九十二頁，編輯于2023年，星期三結(jié)論8(預(yù)流中無增廣路)相加得:h(s)<=h(t)+k<=0+k<=k而k<|V|,所以h(s)<|V|.而根據(jù)定義,h(s)=|V|.矛盾.第五十二頁，共九十二頁，編輯于2023年，星期三預(yù)流推進算法的正確性當(dāng)有溢出結(jié)點時,根據(jù)結(jié)論5,必定可以在它上面施加一個操作.當(dāng)算法停止時,因為無溢出結(jié)點,所以當(dāng)前流是一個合法流,而根據(jù)結(jié)論8,Gf中始終不存在增廣路.根據(jù)最大流最小割定理,當(dāng)Gf中不存在增廣路時,當(dāng)前流是最大流.(算法執(zhí)行了一半時雖然也沒有增廣路,但由于它不是一個合法流,前面的諸多定理都不成立).算法的最優(yōu)性的保證者:對于所有在Ef中的(v,u),均有h(v)<=h(u)+1第五十三頁，共九十二頁，編輯于2023年，星期三更好的預(yù)流推進算法前面的一般預(yù)流推進算法可以實現(xiàn)為O(n^4).其瓶頸是非飽和推進.(非飽和推進是指在推進之后仍舊沒有使(u,v)消失的推進.)通過恰當(dāng)?shù)匕才抨P(guān)鍵操作的順序,可以使總的推進(主要是非飽和推進)和重標(biāo)號的次數(shù)減少.接下來的relabel-to-front算法就用了這個思想.第五十四頁，共九十二頁，編輯于2023年，星期三Relabel-to-frontrelabel-to-front算法維護一個結(jié)點列表,然后依次檢查列表中的結(jié)點.檢查的過程就是:一口氣將所有的贏余推給周圍的人.如果在檢查的時候這個結(jié)點被relabel了,那么他就被移到整個列表的最首部,并且重新從列表首部開始檢查結(jié)點.通過這樣恰當(dāng)?shù)匕才挪僮黜樞?一次性把某個結(jié)點所有的贏余全部推掉),復(fù)雜度降到了O(n^3).第五十五頁，共九十二頁，編輯于2023年，星期三一些定義如果滿足下面的兩個條件,稱(u,v)為可行弧:r(u,v)>0h(u)=h(v)+1可行邊集Ef,h:所有由可行弧組成的集合?？尚芯W(wǎng)絡(luò)Gf,h=(V,Ef,h)第五十六頁，共九十二頁，編輯于2023年，星期三結(jié)論9,10結(jié)論9:可行網(wǎng)絡(luò)中無環(huán).(和結(jié)論8的證明類似,弄一堆式子然后疊加一下,導(dǎo)出矛盾)結(jié)論10:推進操作永遠不會新增可行弧,卻可能使原有的可行弧消失.(根據(jù)可行弧的定義顯然)第五十七頁，共九十二頁，編輯于2023年，星期三結(jié)論11在u被重標(biāo)號之后:1).至少有一條可行弧離開u.顯然.設(shè)v0是u的鄰居中h值最小的那一個,則(u,v0)必定是一條可行弧.2).不可能有可行弧進入u.假設(shè)有一條(w,u).則h(w)=h’(u)+1.根據(jù)輔助定理6,relabel操作至少將結(jié)點的h+1,所以h(w)>h(u)+1.根據(jù)高度函數(shù)必須滿足的條件,(w,u)在relabel前不在Ef中.而relabel操作只改變可行網(wǎng)絡(luò)不改變殘量網(wǎng)絡(luò),(w,u)不可能在relabel前存在于Ef而之后就不存在.第五十八頁，共九十二頁，編輯于2023年，星期三當(dāng)前弧每個結(jié)點有一個鄰居列表和有一個“當(dāng)前弧”的指針,保存當(dāng)前檢查到鄰居列表中的哪一條弧了。初始化時,“當(dāng)前弧”指向與該結(jié)點相連的第一條邊.鄰居列表保存的是所有可能成為可行弧的弧.當(dāng)再次調(diào)用檢查操作時,可以從上一次檢查了一半的地方繼續(xù)檢查.具體請看下面檢查操作的偽代碼:第五十九頁，共九十二頁，編輯于2023年，星期三檢查操作Check(u)Whilee(u)>0doIfcurrent(u)>degree(u)then//當(dāng)沒有可行弧可以推進,該結(jié)點卻仍舊有贏余時,重標(biāo)號.Relabel(u)Current(u)=1ElseIf(u,current(u))是一條可行弧thenPush(u,current(u))//push了之后就不能增加current(u)的值.因為這如果是一次非飽和推進,那再下一次檢查時還是可以沿著這條弧做推進.ElseInc(current(u))第六十頁，共九十二頁，編輯于2023年，星期三當(dāng)前弧的正確性Current是全局變量,當(dāng)某次Check操作結(jié)束時他的值并沒有被清空.比如結(jié)點u有10個鄰居,上次檢查到第7個,那再一次Check(u)的時候就只要從第7個開始檢查就可以了。為什么再一次檢查的時候不要檢查第1-6條邊了?能否證明在再一次檢查的時候他們一定不是可行弧?第六十一頁，共九十二頁，編輯于2023年，星期三當(dāng)前弧的正確性在relabel-to-front算法中,relabel只被Check調(diào)用.當(dāng)“當(dāng)前弧”移動時,移動前它指向的那條弧一定是不可行的.而推進操作不能創(chuàng)造可行弧.只有relabel可以.兩次Check之間沒有relabel操作.所以原先的不可行的弧在第二次Check之前一直是不可行的.第六十二頁，共九十二頁，編輯于2023年，星期三Relabel-to-frontInit-Preflow初始化結(jié)點(除s,t)列表L(任何順序均可)令所有u,Current(u)=1uHead[L]Whileu<>nildoOld-heighth(u)Check(u)Ifh(u)>old-heightthen將u移到L首部//如果h(u)比原先的h高了,說明被relabel,移到隊首.unext(u)第六十三頁，共九十二頁，編輯于2023年，星期三圖例(初始狀態(tài).結(jié)點下方數(shù)字為贏余,N顯示的是鄰居列表,N中紅色的是當(dāng)前弧指針?biāo)诘奈恢?)S-26x12y14z0t06543210(12/12)(14/14)(0/16)(0/7)(0,5)(0,8)(0,10)LxyzNssxyxyzztt第六十四頁，共九十二頁，編輯于2023年，星期三圖例:x被檢查并重標(biāo)號,并被提到L的首部(等于沒提).注意當(dāng)前弧的指針移到了t.x的所有贏余推給了y和t.S-26x0y19z0t76543210(12/12)(14/14)(7/16)(0/7)(5,5)(0,8)(0,10)LxyzNssxyxyzztt第六十五頁，共九十二頁，編輯于2023年，星期三圖例:y正在被檢查.將8單位的贏余推給z之后還是有剩余.S-26x0y11z8t76543210(12/12)(14/14)(7/16)(0/7)(5,5)(8,8)(0,10)LxyzNssxyxyzztt第六十六頁，共九十二頁，編輯于2023年，星期三圖例:一次必須把贏余全部推光.所以y被重標(biāo)號,當(dāng)前弧指針從頭開始查找,找到(y,x)這條可行弧之后進行推進.實際上是把多推的贏余還給了x.因為h(u)<=h(v)+1的保證,它沒有把贏余錯推給s.S-26x5y6z8t76543210(12/12)(14/14)(7/16)(0/7)(0,5)(8,8)(0,10)LxyzNssxyxyzztt第六十七頁，共九十二頁，編輯于2023年，星期三圖例:y還是有贏余.當(dāng)當(dāng)前弧移動到另局列表的尾部時,y再一次被重標(biāo)號,并把贏余還給s.檢查結(jié)束,y被提到L列表的首部.S-20x5y0z8t76543210(12/12)(8/14)(7/16)(0/7)(0,5)(8,8)(0,10)LyxzNssxxyyzztt第六十八頁，共九十二頁，編輯于2023年，星期三圖例:檢查x.注意x的當(dāng)前弧指針已經(jīng)指在t上了.x把贏余推給t.u指針直接后移.(因為x沒有被重標(biāo)號)S-20x0y0z8t126543210(12/12)(8/14)(12/16)(0/7)(0,5)(8,8)(0,10)LyxzNssxxyyzztt第六十九頁，共九十二頁，編輯于2023年，星期三圖例:z被檢查并被提到列表首部.S-20x0y0z0t206543210(12/12)(8/14)(12/16)(0/7)(0,5)(8,8)(8,10)LzyxNxssyxytzzt第七十頁，共九十二頁，編輯于2023年，星期三圖例:u指針從y開始向后移動,直到隊尾也沒有發(fā)現(xiàn)可以檢查的結(jié)點(只有溢出的結(jié)點才能被檢查).算法結(jié)束.S-20x0y0z0t206543210(12/12)(8/14)(12/16)(0/7)(0,5)(8,8)(8,10)LzyxNxssyxytzzt第七十一頁，共九十二頁，編輯于2023年，星期三relabel-to-front的正確性前面我們已經(jīng)證明了一般預(yù)流推進算法的正確性了.因此,現(xiàn)在只要證明,在relabel-to-front算法結(jié)束時,一般預(yù)流推進算法的結(jié)束條件也正好被滿足----即沒有溢出的結(jié)點.第七十二頁，共九十二頁，編輯于2023年，星期三結(jié)論11:L始終拓撲有序?qū)τ贕上的可行網(wǎng)絡(luò)Gf,h,列表L中的結(jié)點始終保持拓撲有序性.一開始的時候,列表中所有結(jié)點(s,t不在列表中)的高度均為0,不存在高度差,所以不存在可行弧.這時列表顯然拓撲有序.一個結(jié)點被relabel之后,就被提到列表的首部.根據(jù)輔助定理11,relabel之后沒有可行弧進入結(jié)點,但有可行弧離開結(jié)點,所以將結(jié)點提到列表首部仍舊使列表滿足拓撲有序.推進操作不能創(chuàng)造可行弧,因此與列表的拓撲有序性無關(guān).第七十三頁，共九十二頁，編輯于2023年，星期三結(jié)論12L中指針u之前的結(jié)點全部是非溢出結(jié)點.當(dāng)一個結(jié)點被檢查之后,它必定沒有贏余,因此將u指針后移不影響上面的性質(zhì).它自己沒有贏余了,但它卻可能將贏余推給了別人.如果推給在L中位置在它后面的結(jié)點不要緊.但如果它把贏余推給了在自己之前的結(jié)點呢?因為L拓撲有序,他若把贏余推給了排在自己前面的結(jié)點,則必定發(fā)生了relabel操作.而如果有relabel,則它已經(jīng)被提到列表的首部了.性質(zhì)依然滿足.這就是算法名:relabel-to-front的由來.第七十四頁，共九十二頁，編輯于2023年，星期三Relabel-to-front根據(jù)一般的預(yù)流推進算法,當(dāng)沒有溢出結(jié)點時算法就結(jié)束并得到一個最大流.而relabel-to-front算法的結(jié)束條件是u指針指向L隊列尾部.根據(jù)輔助定理12,u以前的結(jié)點均非溢出結(jié)點.所以當(dāng)u指向尾部時,所有的結(jié)點均沒有溢出.另外可以證明,算法的復(fù)雜度為O(n^3).第七十五頁，共九十二頁，編輯于2023年，星期三Highest-relabel還可以改進.經(jīng)驗表明,總是檢查高度標(biāo)號最大的結(jié)點，會有比較好的效率.于是對Relabel-to-front進行了一點小修改,得到了highest-relabel算法.第七十六頁，共九十二頁，編輯于2023年，星期三分塊的L列表可以證明,任意結(jié)點的最大的距離標(biāo)號為2n-1.將L列表分成2n個塊,第1塊保存所有高度為0的點,第i+1塊保存高度為I的所有結(jié)點.從最后一塊開始往前找,發(fā)現(xiàn)一個不為空的塊就把這個塊里的結(jié)點全部檢查掉.如果有元素被重標(biāo)號了,那就將他移動到新的塊里,并從那個新的塊的前面開始繼續(xù)往下查找.第七十七頁，共九十二頁，編輯于2023年，星期三分塊的L列表對于可行網(wǎng)絡(luò),分塊L列表是拓撲有序的.因為可行弧(u,v)要求h(u)=h(v)+1,即只有從標(biāo)號高的結(jié)點指向標(biāo)號低的結(jié)點.既只有從后面的塊里的結(jié)點指向前面的塊里的結(jié)點.所以,這種分塊方法仍然保持了整個列表的拓撲有序性.因此,算法結(jié)束時沒有溢出的結(jié)點.因此該算法是正確的.第七十八頁，共九十二頁，編輯于2023年，星期三分塊L列表的實現(xiàn)如果用鏈表，可以只占用O(n)的空間。在內(nèi)存不緊張的情況下，也完全可以用無序數(shù)組，時間效率不比鏈表差,雖然空間是O(n^2)的.無序數(shù)組在刪除的時候，可以用:Delete(i)a[i]a[n]Dec(n)第七十九頁，共九十二頁，編輯于2023年，星期三更多的改進回顧一下上面兩個算法的正確性:1).h是一個合法的高度函數(shù) Gf不存在增廣路2).同一結(jié)點h值保證遞增重標(biāo)號后沒有可行弧進入結(jié)點 列表L永遠拓撲有序Relabel-to-front(highest-relabel)算法正確. 也就是說,只要滿足1).2).兩條,h的值具體怎么變化并不重要.第八十頁，共九十二頁，編輯于2023年，星期三更多的改進可以發(fā)現(xiàn),每當(dāng)重標(biāo)號操作被執(zhí)行,該結(jié)點的當(dāng)前弧的位置就被重置,同時這個結(jié)點被往前提,然后這個結(jié)點后面的結(jié)點又全部得被檢查一遍.也就是說,每次重標(biāo)號操作都很新產(chǎn)生很多工作,我們應(yīng)該盡量減少重標(biāo)號的次數(shù).而h值的具體變化規(guī)則不影響正確性.于是,我們希望h值能增長得快一點.(在滿足h函數(shù)的合法性和單調(diào)遞增性的情況下)第八十一頁，共九十二頁，編輯于2023年，星期三BFS預(yù)處理從前面的圖例中可以發(fā)現(xiàn),有些結(jié)點根本沒