最大流算法及其應(yīng)用-文庫(kù)吧資料
2024-08-28 22:33本頁(yè)面
【正文】 頂點(diǎn)找到的允許弧，只有在修改這個(gè)頂點(diǎn)標(biāo)號(hào)時(shí)才會(huì)更改這個(gè)頂點(diǎn)的當(dāng)前弧。 當(dāng)前弧優(yōu)化 ?可以注意到一個(gè)事實(shí)：如果說(shuō)在某次迭代中從 i出發(fā)的弧 (i,j)不是允許弧，則在頂點(diǎn) i的標(biāo)號(hào)修改之前 (i,j)都不可能是允許弧。 1，這時(shí)候必定無(wú)法再找到增廣路徑。 SAP的優(yōu)化 ?SAP算法有兩個(gè)重要的優(yōu)化： Gap優(yōu)化 和當(dāng)前弧優(yōu)化 。 ? end。 ? end ? else ? if i出發(fā)有弧 then ? d(i)=min{ d(j)+1 | (i,j)在殘留網(wǎng)絡(luò)中 } ? else ? begin ? d(i):=n。 ? if i=t then ? begin ? 沿著增廣路增廣，修改殘留網(wǎng)絡(luò) ? i:=s。 ? Var ? …… ? Begin ? 預(yù)處理流為零流，建立殘留網(wǎng)絡(luò) ? 計(jì)算距離函數(shù) d(i) ? //實(shí)際上一開(kāi)始沒(méi)有必要用 BFS計(jì)算，清零就行了 ? i:=s。當(dāng)找不到允許路的時(shí)候，我們需要修改某些點(diǎn)的 d(i)。 允許弧和允許路 ?如果殘留網(wǎng)絡(luò) Gf中的一條弧 (i,j)滿足d(i)=d(j)+1，我們稱 (i,j)是允許弧，由允許弧組成的一條 st路徑是允許路。最終的時(shí)間復(fù)雜度為 O(n2m)，但在實(shí)踐中，時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)小于理論值（特別是加了優(yōu)化之后），因此還是很實(shí)用的。 最短增廣路算法 ?即每次尋找包含弧的個(gè)數(shù)最少的增廣路進(jìn)行增廣，可以證明，此算法最多只需要進(jìn)行 mn/2次增廣。當(dāng)然我們可以用最基本的搜索（ DFS或 BFS），但是這種方法肯定不夠高效，這時(shí)我們就需要更高效的算法。 最大流算法 ?前面所講的只是求最大流的一種方法，但怎樣高效地實(shí)現(xiàn)還是一個(gè)問(wèn)題。 ?FordFulkerson定理（最小割最大流定理）： 在流網(wǎng)絡(luò)中，最小割的容量等于最大流的流量。此方法（之所以不是算法，是因?yàn)閷?shí)現(xiàn)方法很多）稱為FordFulkerson方法。（證明在此略去，可以參見(jiàn)相關(guān)書(shū)籍） ?根據(jù)增廣路定理，我們可以設(shè)計(jì)出最基本的求最大流的方法，一開(kāi)始將流網(wǎng)絡(luò) G=(V,E)的流 f置為零流，即對(duì)于 (u,v)∈ E時(shí)， f(u,v)=0。（程序?qū)崿F(xiàn)基本都是通過(guò)直接修改殘留網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)增廣的） 二、 最大流和最小割問(wèn)題 最大流問(wèn)題 ?對(duì)于一個(gè)流網(wǎng)絡(luò) G=(V,E)，其流量 |f|的最大值稱為最大流，最大流問(wèn)題就是求一個(gè)流網(wǎng)絡(luò)的最大流。這樣的話，新的流 f仍然滿足流的三條性質(zhì)，并且原流網(wǎng)絡(luò)的流量 |f|增加了。后面求最大流要用到增廣路徑這個(gè)概念。在下面的各種概念和方法中，我們只考慮殘留網(wǎng)絡(luò)中容量大于 0的弧，但是編程時(shí)為了方便還是保留了。定義割 (S,T)的容量為 c(S,T
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1