網(wǎng)絡(luò)流算法介紹與分析學(xué)習(xí)教案

1、會計學(xué)1第一頁，共89頁。第1頁/共89頁第二頁，共89頁。v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)一個簡單的一個簡單的例子例子.網(wǎng)絡(luò)可網(wǎng)絡(luò)可以被想象成以被想象成一些輸水的一些輸水的管道管道.括號內(nèi)括號內(nèi)右邊的數(shù)字右邊的數(shù)字表示管道的表示管道的容量容量,左邊的左邊的數(shù)字表示這數(shù)字表示這條管道的當(dāng)條管道的當(dāng)前前(dngqin)流量流量.第2頁/共89頁第三頁，共89頁。1、容量限制、容量限制: fu,v 0 )令令e(u) = f(V,u),稱為稱為u點的贏點的贏余，直觀地描述，就是余，直觀地描述，就是“流流入的比流出的多多少入的比流出的多多少”。e(v1)=4,e(v2)

2、=3。不斷將溢。不斷將溢出的結(jié)點中的贏余往后繼點出的結(jié)點中的贏余往后繼點推進(jìn)推進(jìn),直到贏余都聚集在直到贏余都聚集在t.第30頁/共89頁第三十一頁，共89頁。v1tsv2(2,2)(4,4)(0,4)(3,3)(2,2)如果多推了一些流量如果多推了一些流量, 我們可以再把它推回來我們可以再把它推回來. (如如e(v2)=3,但這但這3個單個單位的贏余位的贏余(yn y)已經(jīng)已經(jīng)沒地方去了沒地方去了,只能推回只能推回來來.)(沿著后向弧沿著后向弧)這副這副圖是原網(wǎng)絡(luò)而不是殘量圖是原網(wǎng)絡(luò)而不是殘量網(wǎng)絡(luò)網(wǎng)絡(luò),因此沒把后項弧因此沒把后項弧畫出來畫出來)第31頁/共89頁第三十二頁，共89頁。v1tsv

3、2(2,2)(4,4)(0,4)(3,3)(2,2)此時此時e(v2)=3.正確正確(zhngqu)的回推法的回推法是往是往(v2,s)推推1,往往(v2,v1)推推2,然后使得然后使得這這2個單位的贏余可以個單位的贏余可以從從(v1,t)推到推到t上。上。但程序沒有全局觀但程序沒有全局觀,它它萬一往萬一往(v2,s)推了推了3個個單位怎么辦單位怎么辦?我們總不我們總不能嘗試所有的可能性能嘗試所有的可能性吧吧,那樣就變成搜索了那樣就變成搜索了.第32頁/共89頁第三十三頁，共89頁。,推在程序中并無卻別，都是在推殘量網(wǎng)絡(luò)中的一條邊.第33頁/共89頁第三十四頁，共89頁。第34頁/共89頁第三

4、十五頁，共89頁。第35頁/共89頁第三十六頁，共89頁。這個流才重新合法。第36頁/共89頁第三十七頁，共89頁。第37頁/共89頁第三十八頁，共89頁。確性。后面我們將看到這個條件的作用.第38頁/共89頁第三十九頁，共89頁。第39頁/共89頁第四十頁，共89頁。第40頁/共89頁第四十一頁，共89頁。第41頁/共89頁第四十二頁，共89頁。h(u)=h(v)+1.第42頁/共89頁第四十三頁，共89頁。第43頁/共89頁第四十四頁，共89頁。.1)對應(yīng)重標(biāo)號,2)對應(yīng)推進(jìn)(tujn),兩者必能應(yīng)用一個且只能應(yīng)用一個.第44頁/共89頁第四十五頁，共89頁。第45頁/共89頁第四十六頁，

5、共89頁。第46頁/共89頁第四十七頁，共89頁。第47頁/共89頁第四十八頁，共89頁。第48頁/共89頁第四十九頁，共89頁。第49頁/共89頁第五十頁，共89頁。第50頁/共89頁第五十一頁，共89頁。fkkffEvvEvvEvv),(),(),(121101)()(1)()(1)()(12110kkvhvhvhvhvhvh相加得相加得:h(s)=h(t)+k=0+k=k而而k|V|,所以所以h(s) h(u) + 1.根據(jù)高度函數(shù)必須滿足的條件,(w,u)在relabel前不在Ef中.而relabel操作只改變可行網(wǎng)絡(luò)不改變殘量網(wǎng)絡(luò),(w,u)不可能(knng)在relabel前存在于

6、Ef而之后就不存在.第57頁/共89頁第五十八頁，共89頁。第58頁/共89頁第五十九頁，共89頁。不能增加 current(u)的值.因為這如果(rgu)是一次非飽和推進(jìn),那再下一次檢查時還是可以沿著這條弧做推進(jìn).nElse Inc(current(u)第59頁/共89頁第六十頁，共89頁。(zhngmng)在再一次檢查的時候他們一定不是可行弧?第60頁/共89頁第六十一頁，共89頁。第61頁/共89頁第六十二頁，共89頁。第62頁/共89頁第六十三頁，共89頁。S-26x12y14z0t06543210(12/12)(14/14)(0/16)(0/7)(0,5)(0,8)(0,10)L x

7、 y zN s s xy x yz z tt第63頁/共89頁第六十四頁，共89頁。S-26x0y19z0t76543210(12/12)(14/14)(7/16)(0/7)(5,5)(0,8)(0,10)L x y zN s s xy x yz z tt第64頁/共89頁第六十五頁，共89頁。S-26x0y11z8t76543210(12/12)(14/14)(7/16)(0/7)(5,5)(8,8)(0,10)L x y zN s s xy x yz z tt第65頁/共89頁第六十六頁，共89頁。S-26x5y6z8t76543210(12/12)(14/14)(7/16)(0/7)(0

8、,5)(8,8)(0,10)L x y zN s s xy x yz z tt第66頁/共89頁第六十七頁，共89頁。S-20 x5y0z8t76543210(12/12)(8/14)(7/16)(0/7)(0,5)(8,8)(0,10)L y x zN s s xx y yz z tt第67頁/共89頁第六十八頁，共89頁。S-20 x0y0z8t126543210(12/12)(8/14)(12/16)(0/7)(0,5)(8,8)(0,10)L y x zN s s xx y yz z tt第68頁/共89頁第六十九頁，共89頁。S-20 x0y0z0t206543210(12/12)(

9、8/14)(12/16)(0/7)(0,5)(8,8)(8,10)L z y xN x s sy x ytz zt第69頁/共89頁第七十頁，共89頁。S-20 x0y0z0t206543210(12/12)(8/14)(12/16)(0/7)(0,5)(8,8)(8,10)L z y xN x s sy x ytz zt第70頁/共89頁第七十一頁，共89頁。第71頁/共89頁第七十二頁，共89頁。,列表首部仍舊使列表滿足拓?fù)溆行?n推進(jìn)操作不能創(chuàng)造可行弧,因此與列表的拓?fù)溆行蛐詿o關(guān).第72頁/共89頁第七十三頁，共89頁。第73頁/共89頁第七十四頁，共89頁。第74頁/共89頁第七十五頁

10、，共89頁。第75頁/共89頁第七十六頁，共89頁。,新的塊的前面開始繼續(xù)往下查找.第76頁/共89頁第七十七頁，共89頁。時沒有溢出的結(jié)點.因此該算法是正確的.第77頁/共89頁第七十八頁，共89頁。第78頁/共89頁第七十九頁，共89頁。第79頁/共89頁第八十頁，共89頁。.,長得快一點.(在滿足h函數(shù)的合法性和單調(diào)遞增性的情況下)第80頁/共89頁第八十一頁，共89頁。n可以證明,用這個預(yù)處理優(yōu)化過的算法仍然是正確的.第81頁/共89頁第八十二頁，共89頁。sv1v4v3t6543210v2v5第82頁/共89頁第八十三頁，共89頁。sv1v4v3t6543210v2v5第83頁/共89頁第八十四頁，共89頁。sv1v4v3t6543210v2v5第84頁/共89頁第八十五頁，共89頁。sv1v4v3t6543210v2v5第85頁/共89頁第八十六頁，共89頁。sv1v4v3t6543210v2v5第86頁/共89頁第八十七頁，共89頁。n備注中為我的Highest-relabel算法的代碼(帶BFS預(yù)處理