第8卷%第7期 2009年 7月
软件导刊 Software Guide
Vol.8 No.7 Jul. 2009
旅行商问题求解算法综述
高 珩，鲍 鹏
（中国矿业大学 计算机科学与技术学院，江苏 徐州 221116）
摘 要：旅行商问题作为 NP 难题的典型代表，从诞生以来一直都是计算机算法理论研究的热点话题 ，各种针对该问
参考文献：
［1］ 陈国良.遗传算法及其应用［M］.北京：人民邮电出版社，1996. ［2］ 郭靖扬.旅行商问题概述［J］.大众科技，2006（8）. ［3］ 余详宣，崔国华，邹海明.计算机算 法基 础 ［M］.武汉 ：华 中科 技 大
学 出 版 社 ，1998. ［4］ 王剑文. 求解 TSP 问题算法综述 ［J］. 计算 机工 程 与科 学 ，2008
遗传算法求解 TSP 问题的基本步骤如下：①在搜索空间中 随 机 产 生 初 始 种 群 ；② 计 算 每 个 个 体 的 目 标 函 数 ，经 调 整 得 到 相 应 的 适 应 度 值 ；③通 过 遗 传 算 子 操 作 产 生 下 一 代 个 体 ；④ 在 下一代个体的基础上回到步骤②， 记录下每代的最好个体，直 至 达 到 最 大 迭 代 次 数 ；⑤ 输 出 最 好 个 体 ，终 止 整 个 程 序 。
城市且仅一次，如何规划一条路径，使该旅行商的花费最少。 TSP 还是一个典型的组合优化问题，是诸多领域内出现的多种 复杂问题的集中概括和简化形式， 并且已成为各种启发式的 搜索、优化算法的间接比较标准。 因此，快速、有效地解决 TSP 有着重要的理论价值和极高的实际应用价值。
1 求解TSP的算法介绍
还有， 若是作为 db2 的 hv， 就必须类型与 DB2 的类型匹 配，如果一个 9 型的来接受，也会造成错误。 COMP 型的变量常 用于表示半个字或者整个字（主机一个字是 4 个字节），比如半 个字也就是 16BIT，对于有符合的数来说就是－32767-＋32767， 所以可以用 S9（5）COMP 来表示，当然也可以用 S9（4）COMP 来 表示（因为 S9（4）表 示 的 范围 是－9999 到＋9999，一 个 字 节存 不 下，也需要 2 个自己存储），对于一个字就是 S9（8）或者 S9（9）。 详细可以自己计算。
参考文献：
［1］ CAROL BAROUDI.COBOL 从 入 门 到 精 通 ［M］.邱 仲 潘 ，译.北 京 ： 电 子 工 业 出 版 社 ，2000.
［2］ 郭彩 虹，李 伟.程 序 设 计 类 课 程 教 学 改 革 之 我 见 ［J］.浙 江 树 人 大 学 学 报 ，2005（5）. （责任编辑：杜能钢）
0 引言
旅行 商 问 题 （TSP）又 称 为 旅 行 推 销 员 问 题 、货 郎 担 问 题 ， 简称为 TSP 问题。 Gaery 已经证明 TSP 问题是 NP 难题， 它是 VRP 的特例，是最基本的路线问题，该问题可以归结为单一旅 行者由起点出发，通过所有给定的需求点之后，最后再回到原 点的最小路径成本求解问题，可以这样来描述旅行商问题：有 N 个城市由公路相互连通，从任一城市到另外城市都要支付 相应的费用，一个销售商从其中一城市出发，访问其他 N－1 个
步骤 4：因为当前节点是同层同父节点具有最小下界值的 节点，如果当前节点下界值大于或等于 C＊，则不必再搜索当前 节点及其同层同父的活动节点，这样，当前节点的上一层节点 （父节点）被探测尽 ，p←p－1，去掉 P1 中的最后一个工件 ，转 步 骤 6。 否则，转步骤 5；
步骤 5：如果 p＝n，则得到一个较优顺序。 令 P＊＝P1，C＊是当 前节点的下界值，p←p－1，去掉 P1 中最后一个工件，转步骤 6； 否则转步骤 2；
（30）. ［5］ 李敏，吴浪，张开碧.求解旅行商问题的几种算法的比较研究 ［J］.
重 庆 邮 电 大 学 学 报 ，2008（5）. （责任编辑：杜能钢）
遗传算法的优点是可以处理非光滑甚至是离散的问题，为 通用算法，适用范围广，能较容易得到满意解而且处理速度相 对较快，缺点是容易出现早熟现象，需要根据具体问题调整选 择和变异策略。
2 结束语
旅行商问题一直都是业界研究的重点， 其应用范围广，在 许多领域都有其重要的指导意义。 客观地说，目前并不存在一 种求解 TSP 问题的最佳算法 ， 如前文所述的各个算法都有其 应用的局限性：经典算法追求精确解，但是忽略了算法的时空 消耗，可行性不高；而现代流行改进算法则是追求近似解，降低 了算法的时空消耗，但是在求解结果上往往不能让人满意。 笔 者认为今后在 TSP 的算法研究上应该把握 3 个方面：继续改进 已有 TSP 算 法 ；采 用 人 工 智 能 的 思 想 ，创 造 新 的 TSP 算 法 ；集 合各个算法的优点，进行混合 TSP 算法的研究。 目前这些相关 方向业界人士都有所涉及，也都取得了一定成效，相信在不久 的将来，TSP 问题一定会有更好的解决方案。
步 骤 6：若 p≠0，去 掉 P1 中 最 后 一 个 工 件 ，转 步 骤 3； 否 则，算法停止。 C＊是最优目标函数值，P＊是最优顺序。 1.3 模拟退火算法
模拟退火算法是解决 TSP 问题的有效方法之一，其来源于 固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温 时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时 粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到 基态，内能减为最小。 用固体退火模拟组合优化问题，将内能 E 模拟为目标函数值 f，温度 T 演化成控制参数 t，即得到解组合 优化问题的模拟退火算法：由初始解 i 和控制参数初值 t 开始， 对当前解重复 “产生新解→计算目标函数差→接受或舍弃”的 迭代，并逐步衰减 t 值，算法终止时的当前解即为所得近似最 优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过 程。 该算法是一种新的随机搜索方法，是近年来提出的一种适 合于解决大规模组合优化问题的通用而有效的近似算法。与以
作者简介：高珩（1987－），男，山东莱阳人，中国矿业大学计算机科学与技术学院本科生，研究方向为软件工程 ；鲍鹏（1987－），男，江苏徐州人，中国 矿业大学计算机科学与技术学院本科生，研究方向为软件工程。
· 68 ·
软件导刊
2009 年
用穷举法把所有可能的巡回路径全部列出来，最短的一个就是 最优解，这种方法就是枚举法，又称穷举法，它的解是多维的、 多局部极值的、趋于无穷大的复杂解的空间，搜索空间是 n 个 点的所有排列的集合。但这种处理方法只能处理很小规模的问 题，不能在多项式时间内求解。如果有 n 座城市，那么巡游路径 共有（n－1）！ ／ 2 条，计算的时间和（n－1）！ 成正比。 1.2 分支限界法
步骤 1：设置 P＝0，P1＝空集，C＊＝∞。 设当前节点总是与 P1 相对应。 此时，当前节点即根节点；
步骤 2： 计算从当前节点分支得到的各个子节点的下界， 并按下界值由小到大对各子节点排序。 令 p←p＋1；
步 骤 3：如 果 当 前 节 点 被 探 测 尽 ，令 p←p－1，转 步 骤 6。 否则， 设当前层各活动子节点中具有最小下界值的节点为 Q， 则在 P1 末尾加入 Q 对应第 p 位置上的工件 ，此时的当前节点 转为 Q，转步骤 4；
往的近似算法相比，模拟退火算法具有描述简单、使用灵活、运 用广泛、运行效率高和较少受到初始条件约束等优点。 1.4 遗传算法
遗传算法是模拟达尔文生物进化论的自然选择和遗传学 机理的生物进化过程的计算模型，是一种通过模拟自然进化过 程搜索最优解的方法，按照适者生存和优胜劣汰原理，逐代演 化产生出越来越好的近似解。 在每一代，根据问题域中个体的 适应度大小选择个体，并借助于自然遗传学的遗传算子进行组 合交叉和变异，产生出代表新的解集的种群。 这个过程将导致 种群像自然进化一样的后生代种群比前代更加适应于环境，末 代种群中的最优个体经过解码，可以作为问题近似最优解。
题的算法层出不穷。 对相关的代表性算法进行了介绍与总结，在分析各种算法的特点之后，提出了各类算法的改进
方向，对旅行商问题的研究进行了展望。
关键词：旅行商问题；NP 难题；算法综述；改进方向
中 图 分 类 号 ：TP301.6
文 献 标 识ቤተ መጻሕፍቲ ባይዱ码 ：A
文 章 编 号 ：1672-7800 （2009）11－0067－02
1.1 穷举法 TSP 的描述虽然简 单 ，解决 起 来 却 很 困 难 ，最 简 单 思 路 是
6C’，对于 无 符 号 ，最 后 补 个 F 表 示 无 符 合 ，对 于 带 符 合 ，如 果 是正数就是 C，负数就是 D。 所有总长度就是［x ／ 2］＋1。
使用的时候，数值型之间都可以直接进行各类操作。 但需 要注意的是 ，如果对于未赋值的 COMP－3 型，在赋值前做任何 计算操作，将会导致数据例外 ，但对于 zoned decimal 就会才有 缺省值，不会有数据例外。
2 结束语
本文源于多年的基于主机的 COBOL 教学积累， 实际开发 中编程者要多注 意 COBOL 特 有的 数 据 类 型 ，在 IT 业，没 有 哪
一款产品能够像 IBM 的大型主机那样拥有 40 年的历史 ，同时 又在今天竞争激烈的市场中仍然获得用户的青睐。 目前，全世 界绝大部分重要数据仍然存储于 IBM 大型主机之上 ， 全世界 大部分关键程序仍然在 IBM 大型主机上运行 。 虽然传统程序 设计语言的讲授经常会受到诟病， 但 COBOL 语言中比较独特 之处如固定格式、各种繁多的编辑型数据类型以及独特的表处 理方法等，必须进行具体的钻研，同时也应该意识到 COBOL 是 一门既古老又充满活力的语言 ， 它必将伴随 IBM 主机的辉煌 而继续辉煌。 如何根据市场经济发展的需要，从推动我国软件 业建设的角度出发，在软件开发及外包产业上走出一条自主创 新之路，为社会培养出一批能与世界接轨、具有竞争力的高素 质软件人才，还需要不断地探索。