面向云计算框架的最大流算法实现研究.pdf

《面向云计算框架的最大流算法实现研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第203145卷年第6月2期成都大学学报(自然科学版)V_01．34No．2JournalofChengduUniversity(Natura]ScienceEdition)Jun．2015文章编号：1004—5422(2015)02—0144—05面向云计算框架的最大流算法实现研究邓华富(四川省绵阳财经学校，四川绵阳621000)摘要：网络最大流路径搜索是图论中的一种重要方法，在交通路径规划、通信路由寻址等领域具有广泛的应用．然而，随着实际问题规模的增大，抽象出的网络模型越来越复杂，最大流路径的搜索过程也越来越耗时，甚至丧失其时效性．为提高计算速度，对最大流搜索算法进行了改

2、进，并采用MapReduee分布式编程模式实现了该算法．基于开源云计算框架的实验表明，改进的算法及其在云计算平台上的实现，对于大规模网络有着较好的搜索效果和计算性能．关键词：最大流路径；算法：实现；Ha：loop中图分类号：TP301．6；riP：393．06文献标志码iAO引言1最大流理论及可增路计算方法目前，计算机已经成为研究各类问题的有效工一般而言，抽象路网由有向图N(V，L，C)表示．具之一．例如，在交通路径规划领域，具备最大可增其中，结点集为V，边集为L，分别代表路口和路段．流量的出行路径是实现交通科学诱导、缓解拥堵的以C(a)表示a边允许通过的最大流量，C表示所有

3、基础；而在通信等领域，最大可增流路径是实现有效路段最大流量集合．称起始结点为源结点，终止结点路由寻址、避免数据拥塞的前提-2J．该类问题具有为汇结点．根据图论中的最大流理论以及上述定义，通用的数学模型，即从网络中搜索任意2个结点之问题可归结为：在网络的某源一汇结点对间寻求最间的具有最大可增加流量的路径．图论中将这样的大可增路．理论上，可增路是指满足以下条件的路径问题放在抽象的赋权图中研究．赋权图分为有向图P：对任意边，若是P的正向边，则有△a)=和无向图，由结点、边(有向图中称弧)和每条边对应c(a)一．a)>O；若a是P的反向边，则有△a)的权值组成．权值一般代表边上能通过

4、某种物理量=厂(a)>0．其中，厂(a)是路段a的当前流量值，．的最大值，如运输费用、寻址代价等等，它与边的自△厂(o)称为路段a的可增流．对与某一对源一汇结身性质有关．在此基础上，可以计算任意2个结点之点，若存在某条可增路，则可以沿该可增路将网络总间在权值约束下可增加流量最大的路径，该路径称流量增加Af(n)．这也是可增路和可增流名称的来为最大可增路径．将交通流或通信数据流按照最大源．进一步，定义△．厂(P)=min。∈△．厂(a)为路径尸可增路分配，能够平衡网络负载，减少因某局部区域的可增流．在所有可增路中，具有最大可增流的路径拥堵而造成的网络其他资源闲置，进而提高网络利

5、就是需要搜索的最大可增路．图1给出了一个简单用率J．然而，随着科学技术的飞速发展，需要考察的示例．网络中每条有向边上括号里面的值表示该的路网规模越来越大，单机计算时间也超过了可以边的最大流量，而括号之前的值代表当前流量(即当接受的限度，这已经影响到多种实际问题的实时计前交通流量)．图1(A)中虚线所示路径即为一条可算与决策．而近年兴起的云计算思路与模型，为上述增路．该路径上每条边的可增流Af均已标明，显然问题提供了一个可行的解决方案．基于此，本研究从路径可增流△P)=min。E=P△a)=min{6，6，3}最大流理论出发，提出了一种面向云计算框架的最=3．图1(B)中虚线所

6、示路径为含有反向边(一。)大可增路分布式计算方式，并在开源云平台——Ha—的可增路，不属于本研究考虑的范围，予以排除．doop上加以实现．对于理论上的最大流问题，已有一系列经典的收稿日期：2015—03—13．作者简介：邓华富(1959一)，男，讲师，从事计算机算法研究·148·成都大学学报(自然科学版)第34卷networks：Ⅱroatin~basedmodelingapproach[J]．TrampRes4结论PartA：General，1988，22(6)：445—453．本研究从最大流理论出发，回顾了最大可增路【21JayakrishnanR，ChenA，TsaiW

7、K．Freewayandarterial加simulation彻tembeddedindymmicassignment的搜索算法．同时，针对大规模网络计算缓慢的情[JJ．TrampResRec，1999，1678(1)：242—250．况，为提高计算速度，本研究给出了在开源云计算平[3]FordLR，FulkersonDR．Maximalflowthroughanetwork[J]．台——Hadoop上的MapReduce实现方式．基于简单CanJMath，1956，8(3)：399—404．路网的计算