第24卷第12期2014年12月计算机技术与发展COMPUTEＲTECHNOLOGYANDDEVELOPMENTVol．24No．12Dec．2014旅行商问题中巡回路径的数据结构宗德才1，王康康2(1．常熟理工学院计算机科学与工程学院，江苏常熟215500;2．江苏科技大学数理学院，江苏镇江212003)摘要:旅行商问题中巡回路径的数据结构对局部启发式算法的效率起着非常关键的作用。巡回路径的数据结构必须能够查询一条回路中每个城市的相对顺序，并且能够将一条回路中的部分城市逆序。分析了数组表示法、伸展树表示法和两级树表示法表示巡回路径时各种基本操作的实现过程及时间复杂度。数组表示法能够在常数时间内确定一条回路中每个城市的相对顺序，但是最坏情况下完成逆序操作需要Ω(n)时间，不适用于大规模的旅行商问题。伸展树表示法执行查询和更新操作的平摊时间复杂度是O(logn)，适用于极大规模的旅行商问题。而两级树表示法在最坏情况下每一个更新操作的时间复杂度是O(n0．5)，适用于大规模的旅行商问题。关键词:旅行商问题;局部启发式算法;数组;伸展树;两级树:TP311．12文献标识码:A:1673－629X(2014)12－0072－06doi:10．3969/j．issn．1673－629X．2014．12．018DataStructureofTourforTravelingSalesmanProblemZONGDe－cai1，WANGKang－kang2(1．CollegeofComputerScienceandEngineering，ChangshuInstituteofTechnology，Changshu215500，China;2．SchoolofMathematicsandPhysics，激angsuUniversityofScienceandTechnology，Zhen激ang212003，China)Abstract:Thedatastructureoftourforthetravelingsalesmanproblemplaysacriticalroleintheefficiencyoflocalheuristicalgorithms．Thedatastructureoftourmustpermitqueriesabouttherelativeorderofcitiesinthetourandmustallowsectionsofthetourtobere-versed．Theimplementationandtimecomplexityofseveralbasicoperationswhenthetourisrepresentedbyarray，splaytreeandtwo－leveltreeareanalyzed．Thearray－basedrepresentationofatourpermitstherelativeorderofcitiestobedeterminedinsmallconstanttime，butrequiresworst－caseΩ(n)timetoimplementareversal，whichrendersitimpracticalforlargeinstances．Forthedatastructurebasedonsplaytree，allqueriesandupdatestakeamortizedtimeO(logn)，whichisavailableforextremelylarge－scaletravelingsalesmanproblem．Forthedatastructurebasedontwo－leveltreerepresentation，theworst－casetimeforeachupdateoperationisO(n0．5)，whichisavailableforlarge－scaletravelingsalesmanproblem．Keywords:travelingsalesmanproblem;localheuristicalgorithm;array;splaytree;two－leveltree0引言旅行商问题(TravelingSalesmanProblem，TSP)是an)表示访问的第一个城市是城市a1，第二个城市是城市a2，…，访问的最后一个城市是an，最后再回到第1ij=dji时，称为对一个典型的NP难［1］的组合优化问题。假设有n个城市，用1～n对城市进行编号，1表示城市1，2表示城市2，…，n表示城市n。Θ是所有1，2，…，n排列的集合，di，j是城市i到城市j的距离，s=一个城市a的一条巡回路径。当d，，称TSP问题;当di，j≠dj，i时，称为不对称TSP问题。文中提到的TSP问题均是指对称TSP问题。TSP问题可以用数学表达式表示为:(da，aa，aa，a)(1)(a1，a2，…，an)是1，2，…，n的一个排列，(a1，a2，…，mins∈Θ+d122+…+d3n1收稿日期:2014－01－24修回日期:2014－04－28网络出版时间:2014－10－23基金项目:江苏省高校自然科学基础研究项目(13KJB110006);常熟理工学院青年教师基金项目(CST201209)作者简介:宗德才(1979－)，男，江苏常熟人，讲师，硕士，研究方向为智能优化算法、概率论;王康康，副教授，博士，研究方向为智能优化算法、概率论。网络出版地址:://www．cnki．net/kcms/detail/61．1450．TP．20141023．1102．023．html第12期宗德才等:旅行商问题中巡回路径的数据结构·73·求解TSP问题的算法有两类:一类是精确算法，能够求出TSP问题的精确解，但是计算时间是问题规模(城市个数)的指数级，随着问题规模的扩大，将产生组...