一种基于MapReduce模型的并行化TSP算法研究.pdf

《一种基于MapReduce模型的并行化TSP算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、UNIVERSITYOFELECTRONICSCIENCEANDTECHNOLOGYOFCHINA:-·®i±~f!titj(MASTERTHESIS•~~15rMapReducef~~89jffr1t201221060455*A~~m¥~~~m~~~*A~~~m~~*~~~~I~RJt~1~1¥J~JfJtJJ~JW~otliS~Wf%1,~1X~*~§J1j:bo~J.:f7Ftt*Di~t]j8~t-ttr7Y9r,i~xr:r:f-§~~ftl!Ac~~*~1Jf~tts"J1i3fJl:JJ)t~,m/f~~79~~~~Mtt*~~

2、X~ft~m~~~&~~~W~fflM~M~o~~-~I~~~~m*mRm~~ffW~~~Ba~~r:p~y~~~*~~~~~·~~Tfi~~Ma*~~~~m,~m~&~~8"1~J!5E,:fft~~it*ftiJII*lf:*:$1'1~t!L:ttJ:i!52:i'0}Z:8"1~f~f!t~u~£!,ft~~~~~oo~~ooc*Am~~~Wtt*~~~~~&~x~~~~$%~3~A~~ftM$*ff~~,m~*m~~,~~~~~~}!1/JU-¥¥&{*1¥,~[~~t!:~xo~Wfl'$A~~~E3;liJl:p.olfif.

3、f)3fB分类号密级注1UDC学位论文一种基于MapReduce模型的并行化TSP算法研究（题名和副题名）王心阳（作者姓名）指导教师田文洪副教授电子科技大学成都（姓名、职称、单位名称）申请学位级别硕士学科专业计算机应用技术提交论文日期2015.03论文答辩日期2015.04.22学位授予单位和日期电子科技大学2015年06月答辩委员会主席评阅人APARALLELTSPALGORITHMBASEDONMAPREDUCEMODELAMasterThesisSubmittedtoUniversityofElectronicScienceandTec

4、hnologyofChinaMajor:ComputerApplicationTechnologyAuthor:WangXinyangAdvisor:Prof.TianWenhongSchool:SchoolofInformationandSoftwareEngineering摘要摘要TSP问题（TravelingSalesmanProblem），即旅行商问题，是数学领域里面组合优化问题中被广泛研究的著名问题之一。TSP问题在学术研究和实际生产需求中十分重要，同时在物理学、生物学和计算机科学等领域有着广泛的应用。TSP问题是NP-完全问题中很

5、有挑战性的一个问题。目前对于TSP问题的研究多是在单一物理机上使用顺序执行的启发式算法求得近似解，也有少量研究初步在Hadoop平台上基于MapReduce模型实现了一些诸如遗传算法和蚁群算法等新型启发式算法，但都仍然存在不能保证算法的质量、运行不稳定等问题。本论文探索通过并行MapReduce模型高效解决TSP问题。根据以上存在的问题，本文提出基于MapReduce模型的并行化迭代K-OPT算法：首先，本文提出一种基于MapReduce模型并行化求解最小生成树算法，并用于构造TSP初始化路径；该算法充分应用MapReduce模型中可以很容易

6、对数据进行排序的特点对图中的所有边的权重进行排序，结合并行化的克鲁斯卡尔算法求得最小生成树；再将其作为Christofides算法输入求得一条可以用于迭代求解TSP问题算法的初始化路径，其中Christofides算法是目前TSP问题中最好的近似算法之一，其近似比为1.5-opt。其次，以初始路径为基础，提出一种基于MapReduce模型并行化的K-OPT算法，算法利用MapReduce模型可以充分并行化运算的特点，将map函数用于路径的分发和图的读取，reduce函数用于问题的求解，从集群中多节点求得的不同迭代解中筛选出最优解，将其作为下一

7、次迭代的输入。然后，通过对节点数规模较小的完全图进行基于MapReduce模型所有路径的穷举和对一些TSPLIB中的实例进行基于MapReduce模型的大规模随机路径生成以及并行化去冗余操作，然后进行一定的统计和特征分析，本文首次提出了截断广义Beta分布TruncatedGeneralizedBetadistribution(TGB)作为TSP问题中最优路径的概率密度函数，并以此证明了迭代K-OPT算法的近似比，在不断增加迭代次数的情况下，可获得接近优化的结果。最后，通过大量实例测试验证了本文所提算法的性能。关键词：TSP，MapReduc

8、e模型，并行化，广义Beta分布IABSTRACTABSTRACTTheTSPproblem(TravelingSalesmanProblem)isafamousm