基于商空间理论的最大流/最小割问题求解研究
发布时间：2020-12-09 16:52
最大流问题是一种组合最优化的经典问题,紧连运筹学和网络流理论,常应用在现实场景中的复杂问题求解,为决策人员提供关于调度资源以及合理决策的数学依据,在科学与工程领域具有广泛的应用。大数据时代下的计算机以及网络规模都在飞速发展,虽然最大流问题有几十年的研究历史,但人们需要智能高效的方式去处理海量数据,在这个背景下使用经典算法计算大规模网络最大流变得困难。同时,随着计算机网络流量巨幅增加,网络拥塞的隐患尤为显著,最小割集是最终决定网络承载量的边集,也是影响网络通行能力上限的特殊位置,因此,最小割集的求解在具体应用下也有着重要意义。依据面对大量复杂信息人类智能能够把复杂的问题简单化、抽象化、在不同角度进行转换的特点,商空间理论能够模拟人类思考特点将复杂问题转化到不同空间上进行描述分析,有效地简小问题规模,提高求解效率。因此,本文提出将商空间理论应用到最大流以及最小割集的求解中,以简化问题规模,加快求解速度。本文的研究重点在于,如何结合商空间理论(Quotient Space理论)将粒度较细的大规模复杂网络依据其结构信息构建粒度较粗的小规模网络,并在粗粒度的小规模网络上近似求解大规模网络的最大流...
【文章来源】：安徽大学安徽省 211工程院校
【文章页数】：72 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
第一章 绪论
1.1 研究背景及意义
1.2 国内外相关研究现状
1.3 本文主要工作和组织结构
第二章 基本概念、理论知识及算法
2.1 网络流的基本理论
2.1.1 图与网络
2.1.2 网络流的主要概念
2.2 最大流/最小割的基本概念
2.2.1 最大流问题定义
2.2.2 最大流与最小割
2.2.3 增广路
2.3 本文相关算法描述及分析
2.3.1 Ford-Fulkerson算法
2.3.2 Dinic算法
2.3.3 Improved SAP算法
2.3.4 基于F-F标记法求最小割
2.3.5 标签传播算法
2.4 商空间理论概述
2.5 本章小结
第三章 基于商空间模型和标签传播的最大流求解算法
3.1 基本定义和概念
3.2 基于标签传播快速求解最大流的MFLPA算法
3.2.1 MFLPA算法框架
3.2.2 MFLPA算法详述
3.3 实验结果与分析
3.3.1 实验设置与数据来源
3.3.2 实验结果
3.4 本章小结
第四章 基于商空间模型和增广标记的最小割求解算法
4.1 基本定义和概念
4.2 DSM算法
4.2.1 DSM算法思想
4.2.2 DSM算法详述
4.3 实验结果与分析
4.3.1 实验设置与数据来源
4.3.2 实验结果
4.4 本章小结
第五章 总结与展望
5.1 本文总结
5.2 未来展望
参考文献
附录A 图索引
Appendix A Figure Index
附录B 表索引
Appendix B Table Index
致谢
攻读硕士学位期间参与的科研项目与论文
【参考文献】：
期刊论文
[1]几类求解最大流问题算法在运输问题中的应用[J]. 郭鑫龙. 电子制作. 2015(18)
[2]基于粒计算的大数据处理[J]. 徐计,王国胤,于洪. 计算机学报. 2015(08)
[3]分层法求解网络最大流的研究[J]. 赵姝,苏建忠,刘倩倩,张燕平. 计算机研究与发展. 2014(08)
[4]网络分析中求最大流的商空间方法[J]. 郑诚,张铃. 计算机学报. 2015(08)
[5]收缩邻居节点集方法求解有向网络的最大流问题[J]. 赵姝,许显胜,华波,张燕平. 模式识别与人工智能. 2013(05)
[6]复杂网络社团发现算法研究新进展[J]. 骆志刚,丁凡,蒋晓舟,石金龙. 国防科技大学学报. 2011(01)
[7]运输问题国内外研究评述[J]. 王有鸿,费威. 商业时代. 2010(24)
[8]复杂系统层次的内涵及相互关系原理研究[J]. 顾文涛,王以华,吴金希. 系统科学学报. 2008(02)
[9]人工智能的历史与未来[J]. 刘毅. 科技管理研究. 2004(06)
[10]一个科学新领域——开放的复杂巨系统及其方法论[J]. 钱学森,于景元,戴汝为. 自然杂志. 1990(01)
硕士论文
[1]网络流算法的研究与应用分析[D]. 董方.南京邮电大学 2014
[2]基于BSP模型的网络最大流算法的并行化研究与实现[D]. 赵正委.电子科技大学 2014
[3]基于图论的图像分割技术研究[D]. 罗青青.南京邮电大学 2014
[4]最大流算法与应用研究[D]. 陶晓莉.南京邮电大学 2014
[5]网络优化算法及其应用[D]. 程凤敏.西安电子科技大学 2013
[6]最大流及最小费用的算法研究[D]. 白睿.南京邮电大学 2012
[7]计算运筹学在经济管理领域的应用[D]. 何明华.电子科技大学 2008
[8]带容量限制的运输问题研究[D]. 董鹏.华中科技大学 2005
本文编号：2907174
【文章来源】：安徽大学安徽省 211工程院校
【文章页数】：72 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
第一章 绪论
1.1 研究背景及意义
1.2 国内外相关研究现状
1.3 本文主要工作和组织结构
第二章 基本概念、理论知识及算法
2.1 网络流的基本理论
2.1.1 图与网络
2.1.2 网络流的主要概念
2.2 最大流/最小割的基本概念
2.2.1 最大流问题定义
2.2.2 最大流与最小割
2.2.3 增广路
2.3 本文相关算法描述及分析
2.3.1 Ford-Fulkerson算法
2.3.2 Dinic算法
2.3.3 Improved SAP算法
2.3.4 基于F-F标记法求最小割
2.3.5 标签传播算法
2.4 商空间理论概述
2.5 本章小结
第三章 基于商空间模型和标签传播的最大流求解算法
3.1 基本定义和概念
3.2 基于标签传播快速求解最大流的MFLPA算法
3.2.1 MFLPA算法框架
3.2.2 MFLPA算法详述
3.3 实验结果与分析
3.3.1 实验设置与数据来源
3.3.2 实验结果
3.4 本章小结
第四章 基于商空间模型和增广标记的最小割求解算法
4.1 基本定义和概念
4.2 DSM算法
4.2.1 DSM算法思想
4.2.2 DSM算法详述
4.3 实验结果与分析
4.3.1 实验设置与数据来源
4.3.2 实验结果
4.4 本章小结
第五章 总结与展望
5.1 本文总结
5.2 未来展望
参考文献
附录A 图索引
Appendix A Figure Index
附录B 表索引
Appendix B Table Index
致谢
攻读硕士学位期间参与的科研项目与论文
【参考文献】：
期刊论文
[1]几类求解最大流问题算法在运输问题中的应用[J]. 郭鑫龙. 电子制作. 2015(18)
[2]基于粒计算的大数据处理[J]. 徐计,王国胤,于洪. 计算机学报. 2015(08)
[3]分层法求解网络最大流的研究[J]. 赵姝,苏建忠,刘倩倩,张燕平. 计算机研究与发展. 2014(08)
[4]网络分析中求最大流的商空间方法[J]. 郑诚,张铃. 计算机学报. 2015(08)
[5]收缩邻居节点集方法求解有向网络的最大流问题[J]. 赵姝,许显胜,华波,张燕平. 模式识别与人工智能. 2013(05)
[6]复杂网络社团发现算法研究新进展[J]. 骆志刚,丁凡,蒋晓舟,石金龙. 国防科技大学学报. 2011(01)
[7]运输问题国内外研究评述[J]. 王有鸿,费威. 商业时代. 2010(24)
[8]复杂系统层次的内涵及相互关系原理研究[J]. 顾文涛,王以华,吴金希. 系统科学学报. 2008(02)
[9]人工智能的历史与未来[J]. 刘毅. 科技管理研究. 2004(06)
[10]一个科学新领域——开放的复杂巨系统及其方法论[J]. 钱学森,于景元,戴汝为. 自然杂志. 1990(01)
硕士论文
[1]网络流算法的研究与应用分析[D]. 董方.南京邮电大学 2014
[2]基于BSP模型的网络最大流算法的并行化研究与实现[D]. 赵正委.电子科技大学 2014
[3]基于图论的图像分割技术研究[D]. 罗青青.南京邮电大学 2014
[4]最大流算法与应用研究[D]. 陶晓莉.南京邮电大学 2014
[5]网络优化算法及其应用[D]. 程凤敏.西安电子科技大学 2013
[6]最大流及最小费用的算法研究[D]. 白睿.南京邮电大学 2012
[7]计算运筹学在经济管理领域的应用[D]. 何明华.电子科技大学 2008
[8]带容量限制的运输问题研究[D]. 董鹏.华中科技大学 2005
本文编号：2907174
本文链接：https://www.wllwen.com/shoufeilunwen/benkebiyelunwen/2907174.html
