基于树算法的TSP问题的一个界.pdfVIP

杨宏，等：基于树算法的TSP问题的一个界 技术与方法 基于树算法的TSP问题的一个界 杨 宏 ’，唐 艳 ，叶笑飞 ’ (1．复旦大学 管理学院，上海 200433；2．江西蓝天学院，江西 南昌 330098) 摘【 要】对于满足三角不等式的TSP问题 ，已经有了多种算法，对于我们已经知道的树算法而言，一般文献上都已经证明为 一 个手算法，但本文通过分析和证明，得出了该算法的一个更小界：3一。 关【键词 P(旅行商问题)；算法；上界 【中图分类号】F224．0 文【献标识码】A 文【章编号】l0o5—152X(2008)11-0087—02 A BoundforM etricTravelingSalesmanProblem underChristofides Algorithm YANGHong，TANGYan2,YEXiao-fei (1SchoolofManagement，Fudna University，Shanghai200433；2．JiangxiBlueSkyCollege，Nnaehnag330098，China) Abstract：ForthemetricTSP (TravelingSalesmanProblem)，therearemanyalgorithms．Itisknownthathteboundbasedon Christofides’alogrithm is3／2．However,thepapernaalyzesnadprovesna approximateratio3，273／2nformetricTSPHnderChristofides’ algorithm． Keywords：TSP；algorihtm；bound 1 引言 完全图G上的TSP问题。 已经证明TSP问题是一个NP—hard问题，所以很难有求 TSP问题，又称旅行售货商问题，是组合最优化中的著名 解精确解的有效算法 ，人们更多的是发展各种近似算法和启发 难题，也是计算复杂性理论 、图论 、运筹学、最优化理论等领域 式算法，对于近似算法，公共上界直接反映该算法的好坏程度， 是一个重要 的参数 。对于满足三角不等式的TSP问题 ，用 中的一个经典问题，具有广泛的应用背景。 TSP问题的一般描述为：旅行商从驻地出发 ，经所有要去 Christofides算法，已经证明该算法的界为 ，但我们经过研究 的城市一次后返回原地，应如何安排其旅行路线，才能使总的 发现，它的界其实可以更小为：÷一丢 ，其中n为G中包含的 旅行距离(或时间、费用等)最少。 ‘ n 用数学语言对TSP问题的具体描述如下： 点数。 实例：已知有n个城市的集合c={vl，v：，…，v}，正整数d(v_，vJ 表示从 vi(v。c)到vi(vjec)的距离。 2 算法描述及界的证明 问：是否存在一条距离最短的包含所有城市的闭合回路? 若设对于城市集合c= v…vn}的一个访问顺序为T_{tt2…， Christofides算法的具体描述为： n ． 、 一 (