最小割最大流算法的研究与应用

发布时间：2017-06-07 16:23

  本文关键词：最小割最大流算法的研究与应用，，由笔耕文化传播整理发布。

【摘要】：最小割最大流问题是经典组合优化问题之一,遍及于形象及抽象领域,在形象领域中,通信网络两点间的最大流量,交通网络中两地之间的最大车流量都可以转化为最小割最大流模型,在抽象领域中,最小割最大流可以较单纯型等方法更快更方便地解决最优化问题,如在图像分割技术中,使用最小割最大流方法求解能量函数最小化问题并将最小割集映射到原始图像的生成网络中可以得到被分割物体的边缘,因此,研究更快的最小割最大流算法是提高图像处理速度的核心。本文提出了两种最小割最大流新算法并应用于图像分割技术中,做出了一些成果:1.指出增广链算法中增广链利用率低的问题,并基于贪心原则提出了增广链修复最小割最大流算法,在实验中,提出的新算法在NW小世界容量网络和BA无标度容量网络中效率高于Dinic算法及最高标号预流推进算法;2.发现预流推进算法中的回流现象,说明了回流现象会造成算法滞后并随着网络的层次增加产生的影响逐渐增大,为识别并终止回流过程,提出了回流检测最小标号预流推进算法,实验结果证明,新算法能够终止回流过程并得到精确解,在大多数网络中比最高标号预流推进算法更快;3.结合图像分割技术,构造图割网络,将上述两种算法用于基于能量函数最小化的图像分割,这两种新算法不但能够准确分离目标物体,并且较经典算法降低了运行时间,能做到实时处理;4.针对Ford-Fulkerson这类非多项式时间算法,提出了网络容量倍数压缩方法,通过对网络容量的近似调整实现Ford-Fulkerson算法提速。
【关键词】：最小割最大流 增广链修复 回流检测 图像分割 容量压缩
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157
【目录】：

• 摘要4-5
• Abstract5-8
• 第一章 绪论8-12
• 1.1 研究背景及意义8-9
• 1.2 课题研究现状综述9-10
• 1.3 创新点与章节安排10-12
• 1.3.1 创新点10-11
• 1.3.2 章节安排11-12
• 第二章 最小割最大流问题、经典算法及两种网络12-24
• 2.1 图的定义及其概念12-14
• 2.2 最小割最大流问题14-16
• 2.3 深度优先遍历与宽度优先遍历16-17
• 2.4 剩余网络、分层增量网络、距离标号函数与盈余17-18
• 2.5 最小割最大流经典算法18-20
• 2.5.1 Ford-Fulkerson算法18
• 2.5.2 Dinic算法18-19
• 2.5.3 连续最短路增广算法19
• 2.5.4 预流推进算法19-20
• 2.6 NW小世界网络和BA无标度网络20-23
• 2.6.1 NW小世界网络与BA无标度网络概述20-22
• 2.6.2 NW小世界网络和BA无标度网络的容量矩阵生成22-23
• 2.7 本章小结23-24
• 第三章 基于稀疏网络的增广链修复最小割最大流算法24-31
• 3.1 增广链及阻塞流综述24
• 3.2 增广链修复思想24-25
• 3.3 算法步骤25
• 3.4 可行性分析与复杂度分析25
• 3.5 算法示例25-26
• 3.6 算法的网络适应性26-28
• 3.6.1 层次网络的特性26-27
• 3.6.2 层次网络对增广链修复效率的影响27-28
• 3.7 仿真实验28-30
• 3.7.1 实验的参数28
• 3.7.2 实验结果28-30
• 3.8 本章小结30-31
• 第四章 基于预流推进的回流检测最小标号最大流算法31-40
• 4.1 预流推进算法中的回流现象31-32
• 4.2 新算法思想32-33
• 4.2.1 基于贪心的最小标号活跃节点选取32-33
• 4.2.2 回流的判定及终止条件33
• 4.3 算法步骤33-34
• 4.4 可行性分析和复杂度分析34
• 4.5 算法示例34-35
• 4.6 算法拓展35-36
• 4.7 算法的网络适应性36-37
• 4.8 仿真实验37-39
• 4.9 本章小结39-40
• 第五章 基于最小割最大流的图像分割技术40-48
• 5.1 数字图像的定义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 仿真实验45-47
• 5.6 本章小结47-48
• 第六章 基于容量压缩的最大流近似算法48-52
• 6.1 随机变量的分布及中心极限定理48-49
• 6.2 FORD-FULKERSON算法的缺陷49
• 6.3 倍数压缩最小割最大流近似算法49-50
• 6.4 倍数压缩算法的误差估计50
• 6.5 仿真实验50-51
• 6.6 本章小结51-52
• 第七章 总结与展望52-54
• 参考文献54-57
• 附录1 程序清单57-58
• 附录2 攻读硕士学位期间出版的论文58-59
• 致谢59

【相似文献】

中国期刊全文数据库 前10条

1 曹翠珍;最大流问题与突发事件的应对[J];科技进步与对策;2004年09期

2 凌永发;王杰;李正明;;网络最大流问题典型组合算法研究[J];云南民族大学学报(自然科学版);2006年03期

3 张丰;罗罕勋;;一类网络最大流问题的简便算法[J];中国科技信息;2009年07期

4 朱永津,田丰,马仲蕃,蔡茂诚;网络上两类物资联合最大流问题的极流特征[J];中国科学;1974年06期

5 周玉涛;;基于层次网络的最大流问题研究[J];科技广场;2008年01期

6 柴丽琴;王红昌;;网络最大流问题应用实例研究[J];全国商情(理论研究);2013年17期

7 张远福,叶正道,唐静波;一个制造网络的最大流算法[J];工程数学学报;2005年05期

8 毛华;毛晓亮;李斌;;网络最大流部分割矩阵算法[J];计算机科学;2011年12期

9 周隆盛;;计算机用‘自学习’算法求解网络最大流问题[J];郑州大学学报(自然科学版);1986年01期

10 盖宇仙;李方豫;颉栋栋;;一类流量增减最大值可预见的不确定网络最大流的模型与算法[J];兰州交通大学学报;2007年04期

中国重要会议论文全文数据库 前2条

1 刘文涛;张群;陈子毅;;基于网络最大流的瓶颈分析[A];管理科学与系统科学研究新进展——第8届全国青年管理科学与系统科学学术会议论文集[C];2005年

2 史新生;董志强;方志耕;;应用逻辑割树模型求解模糊可靠条件下的网络最大流问题研究[A];面向复杂系统的管理理论与信息系统技术学术会议专辑[C];2000年

中国硕士学位论文全文数据库 前10条

1 杜政均;一种新的最大流算法的研究[D];电子科技大学;2015年

2 刁强强;最大流问题及欧几里德Steiner树问题初探[D];青海师范大学;2016年

3 严子恒;最小割最大流算法的研究与应用[D];南京邮电大学;2016年

4 许显胜;快速求解大规模网络最大流问题的研究[D];安徽大学;2013年

5 景虹;最大流算法的仿真与分析[D];华中科技大学;2009年

6 周广露;不确定图上的最大流研究[D];哈尔滨工业大学;2014年

7 郭玉芬;网络最大流及回收中心选址问题研究[D];湖南大学;2008年

8 孟晓婉;网络最大流算法与应用研究[D];南京邮电大学;2013年

9 陈静;容差修正网络最大流算法研究[D];燕山大学;2009年

10 李天南;基于最大流的车辆容迟网络路由算法研究[D];上海交通大学;2011年

  本文关键词：最小割最大流算法的研究与应用，由笔耕文化传播整理发布。

本文编号：429653