旅行推销员问题的凸包收缩法.pdf

第24卷第 1期 麓学理论与应用 Vo1．24No．1 2004年 3月 MATHEMATICAL THE0RY AND APPLICATIONS Mar．2004 旅行推销员问题的凸包收缩法’ 张飞涟 裴 赞 (中南大学土木建筑学院，长沙，410075) 摘 要 本文提 出一种用凸包收缩来解决旅行推销员问题 。首先形成一个 凸包初始环路 。然后 ，逐个考察 凸 包 内的点，按照增加值从小到大的顺序依次插入，直至考察完所有的点。从而得到一个包含所有点的环路，即 旅行推销员问题 的一个满意解。 关键词 旅行推销 员问题 凸包收缩法 TSP ConvexHullandConstrictionM ethodofTSP ZhangFeilian PeiYun (SchoolofCivilandArchitecturalEngineering，CentralSouthUniversity，Changsha，410075) Abstract ThispaperpresentsaHeuristicAlgorithm--C~nvex Hulland Constriction Algorithm to solve TSP．First，an initialrounding routeofconvex hullisselected．Secondly，checkallpointsinsidetheconvex hullandinsertthem intheroundingrouteaccordingtotheincreasingvalueonebyone．Inthisway，wegeta roundnigroutewithallpoints，viz．acontentsolutionofTSP． Keywords TravelingSalesmanProblem Co nvexHullandCo nstrictionAlgorithm CHCA TSP 1 问题的提出 旅行推销员问题(TSP)是指以给定的，z个城市为顶点集合 一{1，2，…，，z}，以城市i到城 市 的路径为边 (，)组成边集E，组成欧氏意义下的完全图G一{V，E}，其边(，J)上的权值为 城市之间的旅行代价d (，J∈V，d厂一般取为两城市之间的欧氏距离，特别地，d=0，d= d)，则经典TSP就是在图G上找一条长度最短 的哈密尔顿 回路 ，其回路长度为组成它的每边 长度之和。 当TSP问题有 ，z个结点时，不计闭回路的正走向的差别 ，则总的环游在 (，z一1)!／2个 ，如 果利用穷举法 ，并着眼于最坏的情况 ，则可立即得知：其计算复杂性函数厂(，z)属于，z!类型。用 阶的表示符号，其计算量的阶为0(，z!)，即这种原始的穷举解法从计算复杂性考虑是最不好 的。在TSP的研究中，提出许多新 的算法 ，如禁忌有哪些信誉好的足球投注网站算法、模拟退火算法和遗传算法等。这些 算法都不是最优解 。迄今为止，尚未找到TSP的多项式解法 (倾 向的猜测是不存在多项式算 法)。因此 ，TSP成为有代表性的 “NP—hard”．对TSP的求解很重要 的一个部分是寻求启发式 · 刘再明教授推荐 收穑 日期 ；2003年8月29日 第1期 旅行推锖员同题的凸包收缩法 75 算法 。启发式算法通常是有一些直观的想法出发构思而成的，但一般都不能保证获得的解是最 优解 。凸包收缩法属于启发式算法，可以比较简单地得到TSP问题的一个满意解 。 2 凸包收缩法的基本思路及算法 凸包收缩(CHCA)是对TSP问题的一种简化处理 。该算法结合了Clarke与Wright提出的 C—W 节约算法 中的节约值思想和J．P．Noback与R．F．1ove提出的几何法中的凸包思想，以 拓扑图形为基础进行分析 。 2．1 算法依据 根据一般的几何观察可知，最短访问线路应具有以下直观性质： (1)线路 自身