本文關(guān)鍵詞：最小割最大流算法的研究與應(yīng)用，，由筆耕文化傳播整理發(fā)布。

【摘要】：最小割最大流問題是經(jīng)典組合優(yōu)化問題之一,遍及于形象及抽象領(lǐng)域,在形象領(lǐng)域中,通信網(wǎng)絡(luò)兩點(diǎn)間的最大流量,交通網(wǎng)絡(luò)中兩地之間的最大車流量都可以轉(zhuǎn)化為最小割最大流模型,在抽象領(lǐng)域中,最小割最大流可以較單純型等方法更快更方便地解決最優(yōu)化問題,如在圖像分割技術(shù)中,使用最小割最大流方法求解能量函數(shù)最小化問題并將最小割集映射到原始圖像的生成網(wǎng)絡(luò)中可以得到被分割物體的邊緣,因此,研究更快的最小割最大流算法是提高圖像處理速度的核心。本文提出了兩種最小割最大流新算法并應(yīng)用于圖像分割技術(shù)中,做出了一些成果:1.指出增廣鏈算法中增廣鏈利用率低的問題,并基于貪心原則提出了增廣鏈修復(fù)最小割最大流算法,在實(shí)驗(yàn)中,提出的新算法在NW小世界容量網(wǎng)絡(luò)和BA無標(biāo)度容量網(wǎng)絡(luò)中效率高于Dinic算法及最高標(biāo)號預(yù)流推進(jìn)算法;2.發(fā)現(xiàn)預(yù)流推進(jìn)算法中的回流現(xiàn)象,說明了回流現(xiàn)象會造成算法滯后并隨著網(wǎng)絡(luò)的層次增加產(chǎn)生的影響逐漸增大,為識別并終止回流過程,提出了回流檢測最小標(biāo)號預(yù)流推進(jìn)算法,實(shí)驗(yàn)結(jié)果證明,新算法能夠終止回流過程并得到精確解,在大多數(shù)網(wǎng)絡(luò)中比最高標(biāo)號預(yù)流推進(jìn)算法更快;3.結(jié)合圖像分割技術(shù),構(gòu)造圖割網(wǎng)絡(luò),將上述兩種算法用于基于能量函數(shù)最小化的圖像分割,這兩種新算法不但能夠準(zhǔn)確分離目標(biāo)物體,并且較經(jīng)典算法降低了運(yùn)行時間,能做到實(shí)時處理;4.針對Ford-Fulkerson這類非多項(xiàng)式時間算法,提出了網(wǎng)絡(luò)容量倍數(shù)壓縮方法,通過對網(wǎng)絡(luò)容量的近似調(diào)整實(shí)現(xiàn)Ford-Fulkerson算法提速。
【關(guān)鍵詞】：最小割最大流 增廣鏈修復(fù) 回流檢測 圖像分割 容量壓縮
【學(xué)位授予單位】：南京郵電大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O157
【目錄】：

• 摘要4-5
• Abstract5-8
• 第一章 緒論8-12
• 1.1 研究背景及意義8-9
• 1.2 課題研究現(xiàn)狀綜述9-10
• 1.3 創(chuàng)新點(diǎn)與章節(jié)安排10-12
• 1.3.1 創(chuàng)新點(diǎn)10-11
• 1.3.2 章節(jié)安排11-12
• 第二章 最小割最大流問題、經(jīng)典算法及兩種網(wǎng)絡(luò)12-24
• 2.1 圖的定義及其概念12-14
• 2.2 最小割最大流問題14-16
• 2.3 深度優(yōu)先遍歷與寬度優(yōu)先遍歷16-17
• 2.4 剩余網(wǎng)絡(luò)、分層增量網(wǎng)絡(luò)、距離標(biāo)號函數(shù)與盈余17-18
• 2.5 最小割最大流經(jīng)典算法18-20
• 2.5.1 Ford-Fulkerson算法18
• 2.5.2 Dinic算法18-19
• 2.5.3 連續(xù)最短路增廣算法19
• 2.5.4 預(yù)流推進(jìn)算法19-20
• 2.6 NW小世界網(wǎng)絡(luò)和BA無標(biāo)度網(wǎng)絡(luò)20-23
• 2.6.1 NW小世界網(wǎng)絡(luò)與BA無標(biāo)度網(wǎng)絡(luò)概述20-22
• 2.6.2 NW小世界網(wǎng)絡(luò)和BA無標(biāo)度網(wǎng)絡(luò)的容量矩陣生成22-23
• 2.7 本章小結(jié)23-24
• 第三章 基于稀疏網(wǎng)絡(luò)的增廣鏈修復(fù)最小割最大流算法24-31
• 3.1 增廣鏈及阻塞流綜述24
• 3.2 增廣鏈修復(fù)思想24-25
• 3.3 算法步驟25
• 3.4 可行性分析與復(fù)雜度分析25
• 3.5 算法示例25-26
• 3.6 算法的網(wǎng)絡(luò)適應(yīng)性26-28
• 3.6.1 層次網(wǎng)絡(luò)的特性26-27
• 3.6.2 層次網(wǎng)絡(luò)對增廣鏈修復(fù)效率的影響27-28
• 3.7 仿真實(shí)驗(yàn)28-30
• 3.7.1 實(shí)驗(yàn)的參數(shù)28
• 3.7.2 實(shí)驗(yàn)結(jié)果28-30
• 3.8 本章小結(jié)30-31
• 第四章 基于預(yù)流推進(jìn)的回流檢測最小標(biāo)號最大流算法31-40
• 4.1 預(yù)流推進(jìn)算法中的回流現(xiàn)象31-32
• 4.2 新算法思想32-33
• 4.2.1 基于貪心的最小標(biāo)號活躍節(jié)點(diǎn)選取32-33
• 4.2.2 回流的判定及終止條件33
• 4.3 算法步驟33-34
• 4.4 可行性分析和復(fù)雜度分析34
• 4.5 算法示例34-35
• 4.6 算法拓展35-36
• 4.7 算法的網(wǎng)絡(luò)適應(yīng)性36-37
• 4.8 仿真實(shí)驗(yàn)37-39
• 4.9 本章小結(jié)39-40
• 第五章 基于最小割最大流的圖像分割技術(shù)40-48
• 5.1 數(shù)字圖像的定義40-41
• 5.2 圖像分割的一般方法41-43
• 5.2.1 基于梯度（gradient）的圖像邊緣檢測41-42
• 5.2.2 Hough變換42-43
• 5.2.3 種子填充43
• 5.3 最小割最大流圖像分割方法43-45
• 5.4 圖像的分塊處理45
• 5.5 仿真實(shí)驗(yàn)45-47
• 5.6 本章小結(jié)47-48
• 第六章 基于容量壓縮的最大流近似算法48-52
• 6.1 隨機(jī)變量的分布及中心極限定理48-49
• 6.2 FORD-FULKERSON算法的缺陷49
• 6.3 倍數(shù)壓縮最小割最大流近似算法49-50
• 6.4 倍數(shù)壓縮算法的誤差估計(jì)50
• 6.5 仿真實(shí)驗(yàn)50-51
• 6.6 本章小結(jié)51-52
• 第七章 總結(jié)與展望52-54
• 參考文獻(xiàn)54-57
• 附錄1 程序清單57-58
• 附錄2 攻讀碩士學(xué)位期間出版的論文58-59
• 致謝59

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 曹翠珍;最大流問題與突發(fā)事件的應(yīng)對[J];科技進(jìn)步與對策;2004年09期

2 凌永發(fā);王杰;李正明;;網(wǎng)絡(luò)最大流問題典型組合算法研究[J];云南民族大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年03期

3 張豐;羅罕勛;;一類網(wǎng)絡(luò)最大流問題的簡便算法[J];中國科技信息;2009年07期

4 朱永津,田豐,馬仲蕃,蔡茂誠;網(wǎng)絡(luò)上兩類物資聯(lián)合最大流問題的極流特征[J];中國科學(xué);1974年06期

5 周玉濤;;基于層次網(wǎng)絡(luò)的最大流問題研究[J];科技廣場;2008年01期

6 柴麗琴;王紅昌;;網(wǎng)絡(luò)最大流問題應(yīng)用實(shí)例研究[J];全國商情(理論研究);2013年17期

7 張遠(yuǎn)福,葉正道,唐靜波;一個制造網(wǎng)絡(luò)的最大流算法[J];工程數(shù)學(xué)學(xué)報(bào);2005年05期

8 毛華;毛曉亮;李斌;;網(wǎng)絡(luò)最大流部分割矩陣算法[J];計(jì)算機(jī)科學(xué);2011年12期

9 周隆盛;;計(jì)算機(jī)用‘自學(xué)習(xí)’算法求解網(wǎng)絡(luò)最大流問題[J];鄭州大學(xué)學(xué)報(bào)(自然科學(xué)版);1986年01期

10 蓋宇仙;李方豫;頡棟棟;;一類流量增減最大值可預(yù)見的不確定網(wǎng)絡(luò)最大流的模型與算法[J];蘭州交通大學(xué)學(xué)報(bào);2007年04期

中國重要會議論文全文數(shù)據(jù)庫 前2條

1 劉文濤;張群;陳子毅;;基于網(wǎng)絡(luò)最大流的瓶頸分析[A];管理科學(xué)與系統(tǒng)科學(xué)研究新進(jìn)展——第8屆全國青年管理科學(xué)與系統(tǒng)科學(xué)學(xué)術(shù)會議論文集[C];2005年

2 史新生;董志強(qiáng);方志耕;;應(yīng)用邏輯割樹模型求解模糊可靠條件下的網(wǎng)絡(luò)最大流問題研究[A];面向復(fù)雜系統(tǒng)的管理理論與信息系統(tǒng)技術(shù)學(xué)術(shù)會議專輯[C];2000年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 杜政均;一種新的最大流算法的研究[D];電子科技大學(xué);2015年

2 刁強(qiáng)強(qiáng);最大流問題及歐幾里德Steiner樹問題初探[D];青海師范大學(xué);2016年

3 嚴(yán)子恒;最小割最大流算法的研究與應(yīng)用[D];南京郵電大學(xué);2016年

4 許顯勝;快速求解大規(guī)模網(wǎng)絡(luò)最大流問題的研究[D];安徽大學(xué);2013年

5 景虹;最大流算法的仿真與分析[D];華中科技大學(xué);2009年

6 周廣露;不確定圖上的最大流研究[D];哈爾濱工業(yè)大學(xué);2014年

7 郭玉芬;網(wǎng)絡(luò)最大流及回收中心選址問題研究[D];湖南大學(xué);2008年

8 孟曉婉;網(wǎng)絡(luò)最大流算法與應(yīng)用研究[D];南京郵電大學(xué);2013年

9 陳靜;容差修正網(wǎng)絡(luò)最大流算法研究[D];燕山大學(xué);2009年

10 李天南;基于最大流的車輛容遲網(wǎng)絡(luò)路由算法研究[D];上海交通大學(xué);2011年

  本文關(guān)鍵詞：最小割最大流算法的研究與應(yīng)用，由筆耕文化傳播整理發(fā)布。

本文編號：429653