【摘要】：最大流最小截問題屬于一個(gè)組合優(yōu)化問題,經(jīng)過(guò)多年的研究,獲得了大量的的研究成果。同時(shí)最大流最小截問題在大量實(shí)際生活中的網(wǎng)絡(luò)都取得了廣泛的應(yīng)用,并且很多的的工期優(yōu)化、流程控制等管理學(xué)科的問題以及圖像處理中圖割問題都可以轉(zhuǎn)化最大流最小截問題模型求解。本文主要研究?jī)煞N最大流最小截問題的求解算法及其應(yīng)用,做出了如下成果:1.提出了一種改進(jìn)最短增廣鏈算法。在改進(jìn)算法中刪除了原網(wǎng)絡(luò)中在增廣過(guò)程中達(dá)到飽和弧。從而優(yōu)化了算法中的構(gòu)建剩余分層網(wǎng)絡(luò)的過(guò)程。實(shí)驗(yàn)結(jié)果顯示:改進(jìn)算法的效率優(yōu)于傳統(tǒng)算法。2.提出了最大流最小截問題的遺傳算法解法。在算法中主要設(shè)計(jì)了算法中個(gè)體編碼解碼方法、初始群體生成方法、適應(yīng)度計(jì)算方法和選擇交叉變異算子。實(shí)驗(yàn)結(jié)果表明:該算法能夠在穩(wěn)定計(jì)算最大流最小截問題,并且算法效率優(yōu)于傳統(tǒng)算法。3.介紹了最大流最小截問題在圖割技術(shù)中的應(yīng)用。描述了圖割問題與最大流最小截問題模型之間的轉(zhuǎn)換。最后通過(guò)實(shí)驗(yàn),對(duì)圖像進(jìn)行分割。
[Abstract]:The maximum flow minimization problem belongs to a combinatorial optimization problem. After many years of research, a large number of research results have been obtained. At the same time, the maximum flow minimization problem has been widely used in a large number of real life networks, and a lot of time optimization, The problem of flow control and other management disciplines as well as the graph cutting problem in image processing can be solved by transforming the model of maximum flow and minimum cut problem. In this paper, we mainly study two algorithms and their applications for solving the maximum flow and minimum truncation problem, and make the following results: 1. An improved shortest augmented chain algorithm is proposed. In the improved algorithm, saturation arcs are removed from the original network during the expansion process. Thus, the process of constructing the residual hierarchical network in the algorithm is optimized. The experimental results show that the efficiency of the improved algorithm is better than that of the traditional algorithm. A genetic algorithm (GA) method for solving the maximum flow minimum truncation problem is proposed. In the algorithm, the individual coding and decoding method, the initial population generation method, the fitness calculation method and the selection of crossover mutation operator are designed. The experimental results show that the proposed algorithm is more efficient than the traditional algorithm. The application of maximum flow minimization problem in graph cutting technique is introduced. The transformation between the graph cutting problem and the maximum flow minimum truncation problem is described. Finally, the image is segmented by experiment.
【學(xué)位授予單位】：南京郵電大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5;TP18

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 張憲超 ,陳國(guó)良 ,萬(wàn)穎瑜;網(wǎng)絡(luò)最大流問題研究進(jìn)展[J];計(jì)算機(jī)研究與發(fā)展;2003年09期

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

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

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

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

6 馬國(guó)順;直接尋求最小割求解網(wǎng)絡(luò)的最大流問題[J];基建優(yōu)化;1983年05期

7 黃河,黃長(zhǎng)江;關(guān)于層次網(wǎng)絡(luò)最大流問題的一個(gè)算法[J];交通與計(jì)算機(jī);1997年01期

8 凌永發(fā);徐宗本;;一種求解網(wǎng)絡(luò)最大流問題的算法[J];計(jì)算機(jī)科學(xué);2006年06期

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

10 解季萍,楊超,謝剛;網(wǎng)絡(luò)最大流問題和典型阻塞流算法研究[J];西南林學(xué)院學(xué)報(bào);2005年02期

相關(guān)會(huì)議論文 前10條

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

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

3 黃紀(jì)武;毛澤華;李松濤;張錦雄;;SPMD并行查找算法的MPI實(shí)現(xiàn)[A];廣西計(jì)算機(jī)學(xué)會(huì)——2004年學(xué)術(shù)年會(huì)論文集[C];2004年

4 黃紀(jì)武;毛澤華;李松濤;張錦雄;;SPMD并行查找算法的MPI實(shí)現(xiàn)[A];廣西計(jì)算機(jī)學(xué)會(huì)2004年學(xué)術(shù)年會(huì)論文集[C];2004年

5 符麗錦;覃華;鄧海;孫欣;;一種改進(jìn)的Apriori算法的研究[A];廣西計(jì)算機(jī)學(xué)會(huì)2012年學(xué)術(shù)年會(huì)論文集[C];2012年

6 王東鋒;王軍民;陳英武;;模糊定性仿真理論研究與算法實(shí)現(xiàn)[A];'2000系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)交流會(huì)論文集[C];2000年

7 趙唯;;晶粒度評(píng)級(jí)的改進(jìn)算法[A];中國(guó)圖象圖形科學(xué)技術(shù)新進(jìn)展——第九屆全國(guó)圖象圖形科技大會(huì)論文集[C];1998年

8 劉啟文;;可擴(kuò)展的圖形學(xué)算法演示系統(tǒng)的研究[A];’2004計(jì)算機(jī)應(yīng)用技術(shù)交流會(huì)議論文集[C];2004年

9 簡(jiǎn)金寶;;多條增廣鏈上同時(shí)增流的最大流算法[A];管理科學(xué)與系統(tǒng)科學(xué)進(jìn)展——全國(guó)青年管理科學(xué)與系統(tǒng)科學(xué)論文集（第4卷）[C];1997年

10 佘智;蔣泰;朱延生;;基于Type C協(xié)議的防沖突改進(jìn)算法[A];廣西計(jì)算機(jī)學(xué)會(huì)25周年紀(jì)念會(huì)暨2011年學(xué)術(shù)年會(huì)論文集[C];2011年

相關(guān)博士學(xué)位論文 前10條

1 鐘永騰;基于近場(chǎng)MUSIC算法的復(fù)合材料結(jié)構(gòu)健康監(jiān)測(cè)研究[D];南京航空航天大學(xué);2014年

2 劉燕;入侵雜草優(yōu)化算法在陣列天線綜合中的應(yīng)用[D];西安電子科技大學(xué);2015年

3 苗義烽;突發(fā)事件下的列車運(yùn)行調(diào)度模型與算法研究[D];中國(guó)鐵道科學(xué)研究院;2015年

4 楊玉婷;頭腦風(fēng)暴優(yōu)化算法與基于視頻的非接觸式運(yùn)動(dòng)定量分析方法研究[D];浙江大學(xué);2015年

5 劉杰;全局優(yōu)化問題的幾類新算法[D];西安電子科技大學(xué);2015年

6 柏靜;基于多種混合策略的人工蜂群算法改進(jìn)研究[D];山東師范大學(xué);2016年

7 孔翔宇;幾類優(yōu)化問題的人工蜂群算法[D];西安電子科技大學(xué);2016年

8 匡立;分形網(wǎng)絡(luò)的理論、算法及應(yīng)用研究[D];武漢大學(xué);2015年

9 孫磊磊;AP聚類算法研究及其在電子病歷挖掘中的應(yīng)用[D];大連理工大學(xué);2017年

10 單美靜;求解非線性實(shí)代數(shù)系統(tǒng)的混合算法研究[D];華東師范大學(xué);2008年

相關(guān)碩士學(xué)位論文 前10條

1 紀(jì)亞寶;最大流最小截問題的算法研究與應(yīng)用[D];南京郵電大學(xué);2017年

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

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

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

5 雷柳;基于圖模型的DTN網(wǎng)絡(luò)路由算法研究[D];西安電子科技大學(xué);2015年

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

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

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

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

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

，

本文編號(hào)：2121141