快速求解大规模网络最大流问题的研究

发布时间：2021-02-17 06:53

　　网络流理论是运筹学领域取得迅速发展的理论之一。到目前为止,应该说,无论从理论上还是实际应用中,网络流模型都是一个很成熟的模型。它的建立和求解算法的不断改进,为解决很多实际问题提供了十分有用的工具。最大流问题是网络流现象中的特殊问题,它是研究通过一个流通网络的最大流量问题。在网络优化领域,最大流问题是一个经典的组合优化问题。最大流问题是网络流理论的极其重要的研究领域,除了运用于实际网络问题的优化以外,最大流问题在很多科研与应用领域,如电网优化、流量控制、线路优化等和物理、化学、生物以及管理科学和应用数学等基本学科都有着广泛的应用。尽管最大流问题的研究已经持续几十年,该问题的研究进展已经得到了很大的提高,但最大流问题的研究还有很大的提高空间。首先,在算法的理论研究方面,人们还没有研究出一个高效的算法,如何快速求解大规模网络的最大流问题；也没有得到求解算法时间复杂度的准确下界或近似下界。其次,伴随着实际应用问题的网络规模不断扩大,由此而产生的‘状态爆炸问题’使得经典算法以及其它们的改进版本已经不能满足实际问题的需要。再次,受计算机硬件本身限制,对于大规模数据,经典算法甚至不能够求解最大流问题... 

【文章来源】：安徽大学安徽省 211工程院校

【文章页数】：57 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 研究背景及意义
    1.2 国内外研究现状
    1.3 本文主要工作及结构
第二章 最大流问题基本理论及算法
    2.1 网络流理论
        2.1.1 网络流基本概念
        2.1.2 最大流问题定义及相关定理
        2.1.3 残量网络
    2.2 最大流理论经典算法
        2.2.1 增广路算法
        2.2.2 预流推进算法
    2.3 本章小结
第三章 基于压缩社团最大流算法
    3.1 基本定义
    3.2 挖掘社团算法
    3.3 压缩条件的确定
    3.4 社团压缩的过程
    3.5 实验
        3.5.1 实验数据及性能描述
        3.5.2 实验结果
        3.5.3 实验分析
    3.6 本章小结
第四章 基于层次网络最大流算法
    4.1 层次网络定义
    4.2 层次网络最大流算法
    4.3 实验结果及分析
    4.4 本章小结
第五章 总结与展望
    5.1 本文总结
    5.2 未来展望
参考文献
附录A 图索引
AppendixA Figure Index
附录B 表索引
AppendixB Table Index
致谢
攻读硕士学位期间参与的科研项目与发表的论文
导师、作者简介


【参考文献】：
期刊论文
[1]收缩邻居节点集方法求解有向网络的最大流问题[J]. 赵姝,许显胜,华波,张燕平.  模式识别与人工智能. 2013(05)
[2]一种改进的基于最大流的PageRank算法研究[J]. 唐敏.  信息通信. 2013(01)
[3]不确定图最可靠最大流算法研究[J]. 蔡伟,张柏礼,吕建华.  计算机学报. 2012(11)
[4]基于深度优先的一种网络最大流求解法[J]. 赵礼峰,孟晓婉.  计算机技术与发展. 2012(10)
[5]基于社团为粒度的网络分割方法[J]. 何富贵,张燕平,张铃.  南京大学学报(自然科学版). 2010(05)
[6]网络最大流问题研究进展[J]. 张宪超,陈国良,万颖瑜.  计算机研究与发展. 2003(09)

硕士论文
[1]大规模网络最大流问题研究[D]. 华波.安徽大学 2012



本文编号：3037613