基于粒化思想求解大规模网络最大流的研究.doc

签字日期： 摘要为网络最大流问题，针对网络优化算法提出了更高的要求，使得最大流算法能够更好的应用于不同的行业。因此，最大流的研究在新时期依然显得尤为重要，更具有实际意义，在实际应用中有着较为广阔的前景。然而经典算法类型的发展在几十年前已经进入瓶颈时期，近年来，最大流算法在经典算法的基础上有所改进，但是仍然不能适应当今时代大规模网络的发展速度。在人类智能思维中，当遇到复杂问题、难以一次解决的问题时，通常采用逐步求精、由粗到细的方式解决，而粒计算正是这种可以将复杂空间问题转换为多个简单问题的理论。为了保证最大流算法在大规模复杂网络中快速高效的求解，本文提出使用粒计算中粒化的思想来解决最大流问题中的不足。本文的研究重点在于如何通过将一个大规模复杂网络粒化为多个结构简单、便于求解的小型子网络来大幅度减少求解最大流的时间，同时也要保证求解的准确率。首先，根据粒化思想将原网络粒化为多个不同的子网络，形成多个不同的粒层，再分别求解由相邻粒层组成的子网络的最大流作为原网络最大流的估计值，最后发现求解最大流的过程可以并行实现，因此使用多线程调度，使得其并行化。最后的实验结果表明了本文方法的有效性，大幅度降低了求解网络最大流所需时间，同时保证了结果的准确性。 关键词：最大流；网络流；粒计算：粒化；多线程 猻 畇； 实例说明算法可行性分析多线程相关知识介绍算法 网络流理论是图论的重要组成部分，为图论算法提供了必要的理论支持，其情况，例如，现实中的信息流、交通中的车流、电力网络中的电流、物流网络和社交网络中的各种信息流等，每一条网络流中都存在一定的流量限制制约着整个网络。但是在网络中，由于每个点的转运利用率以及配置不同，并不能使得每一条边的转运能力达到最大值。为了使得每一条边的网络流量达到最大流值，无限接近于其容量限制，求解网络最大流问题变得富有意义。网络最大流问题是网络流理论的重要组成，是介于连续型和离散型问题的分界线之上，可以作为特殊的线性规划以及组合优化问题。在过去的几十年前，网络最大流理论迅速发展，解 基于粒化思想求解大规模网络最大流的研究 表经典最大流算法分类预流推进方法预流推进算法大流算法应用到多个不同的网络类型中。例如，门，痬，在年提出了新的基于重标号推进及局部增广重标号算法，时间复杂度达到了鬲。经网络的方法应用到求解最大流问题上。还有于年在问题，并将其应用到约束网络最大流问题【】【】俊辏珼针对静态容量网络还提出了伪流的概念，通过求解网络的最大阻塞割而求得 安徽大学届硕士学位论文基于粒化思想求解大规模网络最大流的研究算法应用到其它的领域中【鏦杲畲罅鞴瓜氲絥在年将最大流问题应用到多视点重建的问题旰杲畲罅饔玫接邢蚱矫嫱缰小、杲畲罅髦械淖畲罅髯钚钣糜诳墒缰衃此网络弧在近十年中，由于社交网络等的出现，每天均出现了大量的信息流以及新增用户，使得网络规模呈现指数级增长趋势，传统的最大流算法已不能适应网络的发展趋势，对最大流问题算法提出了新的要求。本文列举近年来几类最具有代表最初的粒计算于年由醓，他提出了因果、粒化以及组织三 在本文中利用网络空间结构的信息，根据其粒空间的拓扑结构，将大的网络粒化综上所述，经典算法在求解最大流网络时面临着网络规模急剧增加带来的挑战，而其无法在短时间内求解最大流甚至是不可能求解，并行计算的思想解决了大规模网络的问题，但是其应用网络的范围却相对局限，不能应用于所有的网络。现阶段面对大数据网络带来的巨大挑战，以及计算机技术的飞速发展，需要研究者们使用更加快捷的方法求得网络最大流，而粒计算正是模拟了人类思维，逐步求解复杂问题，将大的网络规模粒化为不同的粒化层，因此本文算法利用了粒计算粒化粒化思想以及计算机技术来解决大数据带来的网络规模增长问题。网络最大流问题有着广泛的应用，在社交网络、流言控制、垃圾邮件、社团发掘等网络优化领域中都发挥着巨大的作用。随着大数据时代的到来、社交网络的日益发达，之前的最大流算法已不能适应网络规模的增长速度，不能保证问题求解的实时性需求，因此网络最大流的研究与发展更需要不断改进。综上所述，本文提出了基于粒计算思想的网络最大流算法，通过粒化原网络流图，形成若干个子网络流图，同时本文采取了两种方式处理该子图，第一种是在经过粒计算思想粒化原网络图在单机下运行求解网络最大流，另外一种是经过粒化后，对子图 安徽大学届硕士学位论文基于粒化思想求解大规模网络最大流的研究进行并行求解网络的最大流，作为原图网络最大流估计值的求解。相比于以往算法，本文方法更能够适应当代社会发展需求，可以快速的求解大规模网络的最大流问题，为解决问题实时性提供了解决思路。第五章为总结与展望部分，对本文的工作加以总结，并展望了未来的研究方向。 定义一个网络琌是一个无环路且连通的有向图，并满足下列所通过任意大小的网络流量。 基于粒化思想求解大规模网络最大流的研究弧的容量为原结点乃腥牖娜萘恐陀胨谐龌娜萘恐偷淖钚祷騰 图一个结点转化为两个结点在图论介绍中，网络流问题是基本的常见问题，而在许多问题中都存在流量问题，它们基本都可以转化为网络流问题。例如，在公路的网络图中存在车辆流，在社交网络等系统中有信息流，在城市供水、地下管道网络中有水流，银行金融机构网络中有现金流等。而从网络流的求解需求角度出发，在现实的加权网络中，网络流问题又可以被分为几种不同的方面：网络最大流问题，最小费用最大流问题、有区间流量限制的网络的最大流最小流问题等。而网络流算法除了解决以上问题之外，还可以解决一些图论问题中的其它问题，例如求解网络的连通度问题，网络的边连通度问题，网络的匹配度问题等。本节将介绍网络基础理论以及它的基本算法。定义网络，珻械囊桓隹尚辛魇侵敢桓龊齠定义在网络中的边希琭的要求为【俊】： 基于粒化思想求解大规模网络最大流的研究此时，网络流牧髁恐滴或，而其中的最大可行流值亲魍鏕的最大可行流值，即最大流。突。纯杀硎酒淇尚辛鱢，；潜突。纯杀硎酒淇尚辛，；懔骰。纯杀硎酒淇尚辛鱢，；橇懔骰。纯杀硎酒淇尚辛鱢，。 定义在网络代琧，存在一条稰，其中璿；粼赑或者后向弧；而剩余的弧为路系幕。图一个单源单汇网络下面将给出关于求解网络最大流两种方法的定义。 安徽大学届硕士学位论文基于粒化思想求解大规模网络最大流的研究可以将当前的可行流值黾游8蟮牧髦祌，具体方法如下：杂诘鼻暗膄值，若皇粲谠龉懵肪叮騠值不变；上述两个条件时的最小值。定义在给定的网络流图心珻目尚辛鱢中，对于弧，存在定义假设在给定的容量网络流图，珻校龆訡进行残留容量修改，形成新的网络流图化珻粼谠鏕中，存在弧，且瑅瑅蛟谛碌耐鏕中存在一条弧，遶籪，同时对于琕幕剐枰T黾右惶趸，瑄淙萘縞“，。此时新的网络流图莆2辛敉纾蛘呤嗤。为该网络的最大流值。定理在一个流网络代珻校嬖谝豢尚辛鱢当且仅当此网络中关于定理已在前一小节具体介绍，下文将针对最大流最小割原理作具体 是一个畉割。绲淖畲罅髁课猣；的值等于网络中最小割的值； 安徽大学届硕士学位论文基于粒化思想求解大规模网络最大流的研究涑鲎畲罅髦礷。算法：预留推进算法【。粼诓辛敉鏕中存在活跃结点则转弧舨淮嬖谠蜃；涑鲎畲罅髦礷。 算法后将原子粒分类形成不同的结点集作为颗粒，而每一个颗粒中包含粒数 基于粒化思想求解大规模网络最大流的研究以及与喙氐谋逧组成，颗粒结构则由不同的组成，算法得出的层次网络谀：畔嗟牧；停蒢提出，在庞大复杂的人文学科系统中的粒子由于其相似性以及一些功能等无区别性，导致了粒子的模糊性。此类模型的粒子关系主要使用规则来表示，是在用广义约束的方式来构造与定义其中的基本粒子。同时，人类认知也有着重要作用，包括了粒度、组织、因果关系。主要用于模糊控制，用隶属度衡量对象，不适合进行网络结构问题的粒其主要思想为利用商结构来构建等价关系，粒化论域求解复杂问题。在商空间理论中，等价关系决定了粒子所属粒层以及商结构属性，同时在商空间模型中还有两条性质，即保真原理和保假原理。面对复杂问题求解时，商空间理论首先选取粗粒度的空间，若在粗粒度空间中命题无解，则在细粒度空间中更无解：同理保真原理也可以减少问题的复杂度。商空间模型与上述两类模型不同的是其粒化的除了以上三类还有其他一些粒计算模型存在，但是目前除了基于商空间的粒 粒子的计算则可表示为以粒子为基础运算对象，对粒子进行推理求解的过程。在粒计算的过程中，运算对象包括了粒子、粒层以及粒层相互之间的关系，其主要包括：粒子的确定，粒子作为复杂问题的原语，是粒计算最为基本的单位；粒层映射，针对同一个复杂问题，通过不同的粒层映射方式，可以形成不同的粒层，则可表示不同的粒度关系，形成了不同细节描述；粒的转换，粒度的转换表示了通过不同的粒层映射关系可以将粗粒度变得更加具体，也可以将细粒度变得更为复杂；粒子计算，而此处的粒子计算就表达了上述粒的转换的具体计算方法；属性保持，通过不同的粒化，形成了不同的粒层，而粒子在这些 安徽大学届硕学位论文基于粒化思想求解大规模网络最大流的研究 本章主要针对随着网络规模的指数级增长，而经典算法以及改进算法不能高效的解决网络最大流的求解问题，因此本章结合了粒计算理论原理，在单机的情解大规模网络的最大流所需时间，提出新的改进，第一步粒化原单源单汇网络并形成粒层，第二步处理相邻粒层及将由相邻粒层组成的子网络处理形成单源单汇子网络流图，第三步对子图使用经典算法求解子图最大流，最后根据网络流原理合成其中的最小值为整个网络的最大流估计值，本章最后的实验结果表明了本章算法的有效性。 安徽大学届硕士学位论文定义对网络中的结点辶礁鍪粜圆问齠蚮，同时，琕，。同时存在边，其最短有向路径长度分别图一个粒层次网络 面对大规模网络的到来，经典算法的使用范围已日益缩小，其适用的网络结点规模的数量级只能局限于数百以及数千。当网络的结点达到数万，弧数达到数十万时，经典算法求解网络的最大流变得尤为复杂，甚至有时是不可能的。之后虽然有大量的研究者改进了经典最大流算法，但是由于当时的网络规模并没有出现急剧增长，因此研究者们大多数只专注于对经典算法的局部改进、或者预对预流推进的标号方式进行改进。当现阶段网络的结点的规模达到数十万，甚至数亿、弧数的规模达到数十亿时，经典算法的时间复杂度变得尤为巨大。在单机的情况下，经典算法在处理结点规模较大的网络时，需要大量时间有时还会出现死机的情况。 基于粒化思想求解大规模网络最大流的研究图粒层次网络 首先，在本节第一部分将给出粒层次网络以及粒层次的构造算法，在算法的过程中，主要使用了广度优先搜索方法确定粒层次结点集，之后再根据粒层次结点集确定粒层次网络。具体算法如下所示：算法：粒层次网络以及粒层次结点集构造。瑄瑅唬襲仨，即求出的出弧的所有粒锤耂集合，加入已经遍历过的粒；同时为了进入下一步循环令篿，最后转入判断是否可以继续；从算法可以看出，算法的空间复杂度相对简单，只需能够存储每个 安徽大学届硕士学位论文基于粒化思想求解大规模网络最大流的研究后求出的对应粒层次空间网络和粒层次结点集。从算法的求解过程中不难发现，在图的粒层次网络中只存在着以下 表示此种弧的怯赏涣憬岬阈纬傻幕。虎鄞嬖诨琕瑄，点集的弧。经过算法之后，粒层次网络中的弧的存在形式只有以上几种，但是去除任意一个其中的割集，网络流将不能从絫。由定理可知，在任意的网络中，其任意一割集的容量之和都大于或等于若蜃5裨蜃5；舜膆表示的是在算法中求解 安徽大学届硕士学位论文基于粒化思想求解火规模网络最大流的研究结点集最为合适。例图和图给出了关于图使用算法的全过程。 图粒层次子网络。的处理过程图层次子网络的处理过程通过算法得出了若干个小型粒层次子网络，有虚拟的单源单汇结点，可算法：求解粒层次子网络最大流跏蓟痠，提取粒层次子网络； 安徽大学届硕士学位论文基于粒化思想求解大规模网络最大流的研究没有因为存在多个粒层次子网络而产生多个存储空间，可以重复使用。算法跏蓟痠； 提取出粒层次结点集琕，利用算法构建出新的粒层层次网络的少于经典算法产生的空间复杂度。实例说明例计算如图所示的粒层次网络的最大流值。 基于粒化思想求解大规模网络最大流的研究例计算如图所示的修改后的粒层次网络的最大流值，将，的容求得的最大流值。而此粒层次网络使用经典算法求得的最大流值为，其最 配置环境。 基于粒化思想求解大规模网络最大流的研究表合适的网络数据集的结果 相对稳定。对规模相近的网络岬懔捅呤枷嗨，粒化的粒层次子网络越多雌淞仍叫，本文算法的运行时间越少，最大流的误差仍控制在很小的范围内。如表所示，对于粒结点数和边数相近的网络，复杂网络粒化的粒层次子网络数多了叮湎嘤脑诵惺奔湟布跎賜倍，而最大流的误差跟粒度的大小则没有必要的联系。 安徽大学届硕士学位论文 表网络数据集的结果测试用例 中的粒层次网络数相对较少，计算求得的最大流估计值的误差也相对较小。因此 基于粒化思想求解大规模网络最大流的研究鬃粪 对稠密度较高的网络其运行时间更低。络最大流求解的过程适当并行化。 安徽大学届硕士学位论文基于粒化思想求解大规模网络最大流的研究算法可行性分析本文在前一章充分的分析了粒化算法的可行性，通过实验数据表明，粒化算法确实可行，相比经典算法和同类较好的最大流算法有一定的优势。但是，分析算法的具体过程不难发现，算法和还存在可以改进的空间，此两个算法相互之间没有无求解逻辑顺序，因此，可以对粒层次子网络利用并行思想将算法和两个过程并行执行。类来支持将一个大任务拆分为多个小任务，并将这些小任务并行执种特殊的线程池。 小节。通过算法粒层次网络以及粒层次结点集构造，可得到一个粒层次网络 安徽大学届硕士学位论文基于粒化思想求解大规模网络最大流的研究愦渭瘂土愦渭淖畲笾礹。算法：求解粒层次子网络最大流；紫扰卸值为的倍数，令痩处硎久扛龊诵枨笪窀鍪跏蓟痠，表示已执行的任务数，为计数器；瓼籆甁籭；舜膄循环可理解为同时调用 第一章绪论此处硎久扛龊诵枨笪窀鍪跏蓟痠，表示已执行的任务数，为计数器；瓼籆甁籭；舜膄循环可理解为同时调用个核使用算法和处理第隽愦巫油纾鞢甁表示返回 安徽大学届硕士学位论文基于粒化思想求解大规模网络最大流的研究甋舜砥鳎诖妫，在位系统下的，法的实验数据，充分证明了算法的有效性。表含较少粒层次结点集的网络产生的实验结果同样，表的数据结果也可以看出算法也是不适用于粒化度较低测试用例表的实验结果表明了算法的有效性，同样的适合于粒化较好的 测试用例“本章小结 安徽大学届硕士学位论文基于粒化思想求解大规模网络最大流的研究度较高的网络其运行时间更低。