最小割最大流算法的研究與應(yīng)用.pdf

1、最小割最大流問(wèn)題是經(jīng)典組合優(yōu)化問(wèn)題之一，遍及于形象及抽象領(lǐng)域，在形象領(lǐng)域中，通信網(wǎng)絡(luò)兩點(diǎn)間的最大流量，交通網(wǎng)絡(luò)中兩地之間的最大車流量都可以轉(zhuǎn)化為最小割最大流模型，在抽象領(lǐng)域中，最小割最大流可以較單純型等方法更快更方便地解決最優(yōu)化問(wèn)題，如在圖像分割技術(shù)中，使用最小割最大流方法求解能量函數(shù)最小化問(wèn)題并將最小割集映射到原始圖像的生成網(wǎng)絡(luò)中可以得到被分割物體的邊緣，因此，研究更快的最小割最大流算法是提高圖像處理速度的核心。
　　本文提出了

2、兩種最小割最大流新算法并應(yīng)用于圖像分割技術(shù)中，做出了一些成果：
　　1．指出增廣鏈算法中增廣鏈利用率低的問(wèn)題，并基于貪心原則提出了增廣鏈修復(fù)最小割最大流算法，在實(shí)驗(yàn)中，提出的新算法在NW小世界容量網(wǎng)絡(luò)和BA無(wú)標(biāo)度容量網(wǎng)絡(luò)中效率高于Dinic算法及最高標(biāo)號(hào)預(yù)流推進(jìn)算法；
　　2．發(fā)現(xiàn)預(yù)流推進(jìn)算法中的回流現(xiàn)象，說(shuō)明了回流現(xiàn)象會(huì)造成算法滯后并隨著網(wǎng)絡(luò)的層次增加產(chǎn)生的影響逐漸增大，為識(shí)別并終止回流過(guò)程，提出了回流檢測(cè)最小標(biāo)號(hào)預(yù)流推進(jìn)

3、算法，實(shí)驗(yàn)結(jié)果證明，新算法能夠終止回流過(guò)程并得到精確解，在大多數(shù)網(wǎng)絡(luò)中比最高標(biāo)號(hào)預(yù)流推進(jìn)算法更快；
　　3．結(jié)合圖像分割技術(shù)，構(gòu)造圖割網(wǎng)絡(luò)，將上述兩種算法用于基于能量函數(shù)最小化的圖像分割，這兩種新算法不但能夠準(zhǔn)確分離目標(biāo)物體，并且較經(jīng)典算法降低了運(yùn)行時(shí)間，能做到實(shí)時(shí)處理；
　　4．針對(duì)Ford-Fulkerson這類非多項(xiàng)式時(shí)間算法，提出了網(wǎng)絡(luò)容量倍數(shù)壓縮方法，通過(guò)對(duì)網(wǎng)絡(luò)容量的近似調(diào)整實(shí)現(xiàn)Ford-Fulkerson算法提速