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

摘要

网络流理论是运筹学领域取得迅速发展的理论之一。到目前为止，应该说，无论从理论上还是实际应用中，网络流模型都是一个很成熟的模型。它的建立和求解算法的不断改进，为解决很多实际问题提供了十分有用的工具。最大流问题是网络流现象中的特殊问题，它是研究通过一个流通网络的最大流量问题。在网络优化领域，最大流问题是一个经典的组合优化问题。最大流问题是网络流理论的极其重要的研究领域，除了运用于实际网络问题的优化以外，最大流问题在很多科研与应用领域，如电网优化、流量控制、线路优化等和物理、化学、生物以及管理科学和应用数学等基本学科都有着广泛的应用。尽管最大流问题的研究已经持续几十年，该问题的研究进展已经得到了很大的提高，但最大流问题的研究还有很大的提高空间。
　　 首先，在算法的理论研究方面，人们还没有研究出一个高效的算法，如何快速求解大规模网络的最大流问题;也没有得到求解算法时间复杂度的准确下界或近似下界。其次，伴随着实际应用问题的网络规模不断扩大，由此而产生的‘状态爆炸问题'使得经典算法以及其它们的改进版本已经不能满足实际问题的需要。再次，受计算机硬件本身限制，对于大规模数据，经典算法甚至不能够求解最大流问题。因此，关于最大流问题的研究具有十分重要的理论意义和实用价值。
　　 本文的研究重点在于，在保证计算误差的条件下，如何简化网络规模与降低计算量，从而达到降低计算规模、快速求解的目的。首先，通过获取网络中的特定结构，根据该特定结构的流量信息分析，进而对特定结构进行选择性压缩，以降低网络规模，构成目标网络，最终利用经典算法求解最大流问题。基于这种思想，本文提出了基于压缩社团求解最大流的算法。其次，提出网络分层的概念，对源网络中的节点进行分层，构造出源网络对应的分层网络，在层次网络中计算相邻层节点之间的流量，最后以局部最大流值的最小值作为全局的最优值，从而对源网络的最大流进行快速有效的估计，减少计算时间。两种算法在一定程度上降低了算法时间复杂度，并且能够在误差允许范围内，精确求解初始网络最大流问题。在国际公认数据集上的实验结果表明了所提出算法的有效性与高效性。
　　 纵观全文，本文的主要工作如下:
　　 1.阐述了最大流问题研究、应用背景及发展现状，提出了经典算法无法应对的挑战。简单介绍了网络流理论、定理、经典最大流算法及其改进版本，并对以上所述算法进行一定的研究与分析。
　　 2.基于压缩网络的思想提出了:基于压缩社团求解最大流的方法，通过获取网络中的特定结构，根据该特定结构的流量信息分析，进而对特定结构进行选择性压缩，以降低网络规模，构成目标网络，最终利用经典算法求解最大流问题，该算法能够在一定程度上降低网络规模且能够精确求解出源网络的最大流。
　　 3.基于层次网络的最大流方法。提出网络分层的概念，对源网络中的节点进行分层，构造出源网络对应的分层网络，同时结合最大流最小割定理，在层次网络中计算相邻层节点之间的流量，从而对源网络的最大流进行快速有效的估计，减少计算时间。对两种算法的流程进行详细阐述，给出了在国际公认数据集上的实验结果，最终对实验结果进行了理论分析。

目录

声明

摘要

第一章 绪论

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

致谢

攻读硕士学位期间参与的科研项目与发表的论文

导师、作者简介