论文部分内容阅读
网络最大流问题是网络流理论的重要组成,是介于连续型和离散型问题的分界线上,可作为特殊的线性规划以及组合优化问题。其在现实的实践应用中,例如现实中的信息流、交通中的车流、电力网络中的电流、物流网络和社交网络中的各种信息流等,网络流都有着对应的权重大小,求解网络最大流问题变得富有意义。在过去的几十年中,网络最大流理论迅速发展,解决了运筹学以及计算机科学中的诸多问题。而在如今的社交网络中,已有超过6亿的社交网络用户,4.2亿的移动互联网用户,每天产生巨大的网络数据,同时在新兴行业,例如电子商务的350亿交易量以及因此而产生的大量的物流业交易,而这些问题都可以转化为网络最大流问题,针对网络优化算法提出了更高的要求,使得最大流算法能够更好的应用于不同的行业。因此,最大流的研究在新时期依然显得尤为重要,更具有实际意义,在实际应用中有着较为广阔的前景。然而经典算法类型的发展在几十年前已经进入瓶颈时期,近年来,最大流算法在经典算法的基础上有所改进,但是仍然不能适应当今时代大规模网络的发展速度。在人类智能思维中,当遇到复杂问题、难以一次解决的问题时,通常采用逐步求精、由粗到细的方式解决,而粒计算正是这种可以将复杂空间问题转换为多个简单问题的理论。为了保证最大流算法在大规模复杂网络中快速高效的求解,本文提出使用粒计算中粒化的思想来解决最大流问题中的不足。本文的研究重点在于如何通过将一个大规模复杂网络粒化为多个结构简单、便于求解的小型子网络来大幅度减少求解最大流的时间,同时也要保证求解的准确率。首先,根据粒化思想将原网络粒化为多个不同的子网络,形成多个不同的粒层,再分别求解由相邻粒层组成的子网络的最大流作为原网络最大流的估计值,最后发现求解最大流的过程可以并行实现,因此使用多线程调度,使得其并行化。最后的实验结果表明了本文方法的有效性,大幅度降低了求解网络最大流所需时间,同时保证了结果的准确性。本文的主要工作可以概括为:1.首先介绍了本文在当前社会下的研究背景及意义,同时介绍了主题最大流求解以及主要方法粒化思想现阶段各自的研究现状。2.为了更好地理解本文的方法,第二章介绍了最大流问题的基础知识以及一些基本算法,同时还介绍了粒计算思想以及粒计算基本原理在本文中的应用。3.提出本文算法,基于粒化思想的求解网络最大流算法,介绍了算法的相关概念定义以及算法的主要过程,最后给出实验结果,验证了算法的有效性。4.在算法过程中发现算法的不足之处,并在后文给出其改进方法,将粒化之后的子网络求解最大流部分采用多线程化求解,同时也给出了实验结果,验证了算法的有效性。