最小割最大流算法的研究與應用.pdf

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

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

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