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

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

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

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

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

5、共89頁(yè)。第46頁(yè)/共89頁(yè)第四十七頁(yè)，共89頁(yè)。第47頁(yè)/共89頁(yè)第四十八頁(yè)，共89頁(yè)。第48頁(yè)/共89頁(yè)第四十九頁(yè)，共89頁(yè)。第49頁(yè)/共89頁(yè)第五十頁(yè)，共89頁(yè)。第50頁(yè)/共89頁(yè)第五十一頁(yè)，共89頁(yè)。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頁(yè)/共89頁(yè)第五十八頁(yè)，共89頁(yè)。第58頁(yè)/共89頁(yè)第五十九頁(yè)，共89頁(yè)。不能增加 current(u)的值.因?yàn)檫@如果(rgu)是一次非飽和推進(jìn),那再下一次檢查時(shí)還是可以沿著這條弧做推進(jìn).nElse Inc(current(u)第59頁(yè)/共89頁(yè)第六十頁(yè)，共89頁(yè)。(zhngmng)在再一次檢查的時(shí)候他們一定不是可行弧?第60頁(yè)/共89頁(yè)第六十一頁(yè)，共89頁(yè)。第61頁(yè)/共89頁(yè)第六十二頁(yè)，共89頁(yè)。第62頁(yè)/共89頁(yè)第六十三頁(yè)，共89頁(yè)。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頁(yè)/共89頁(yè)第六十四頁(yè)，共89頁(yè)。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頁(yè)/共89頁(yè)第六十五頁(yè)，共89頁(yè)。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頁(yè)/共89頁(yè)第六十六頁(yè)，共89頁(yè)。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頁(yè)/共89頁(yè)第六十七頁(yè)，共89頁(yè)。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頁(yè)/共89頁(yè)第六十八頁(yè)，共89頁(yè)。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頁(yè)/共89頁(yè)第六十九頁(yè)，共89頁(yè)。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頁(yè)/共89頁(yè)第七十頁(yè)，共89頁(yè)。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頁(yè)/共89頁(yè)第七十一頁(yè)，共89頁(yè)。第71頁(yè)/共89頁(yè)第七十二頁(yè)，共89頁(yè)。,列表首部仍舊使列表滿足拓?fù)溆行?n推進(jìn)操作不能創(chuàng)造可行弧,因此與列表的拓?fù)溆行蛐詿o(wú)關(guān).第72頁(yè)/共89頁(yè)第七十三頁(yè)，共89頁(yè)。第73頁(yè)/共89頁(yè)第七十四頁(yè)，共89頁(yè)。第74頁(yè)/共89頁(yè)第七十五頁(yè)

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