旅行商问题是由美国 RAND 公司在 1948 年最早引入。RAND 的知名度以及线性规划这 一新颖的方法的使用，使得多旅行商问题成为经典的难题[32]。 TSP问题要从所有可能的路 线中求取最小消费或最短距离的访问路程。而从起点出发的访问路线一共有(n-1)!条。为除了 起点之外的（n-1）个点的组合，所以旅行商问题可以总结为排列组合问题。排列组合问题一 般比子集合的选择问题的求解难很多。这是因为这 n 个点有 n!种排列方式，相比之下子集合

个数却小得多。通过枚举(n-1)!条路线，从而从其中找到成本最小或路径最短的访问路线的算 法，其消耗的时间为 O(n!)。

解决 TSP 问题常用的方法主要有枚举法思想、回溯法思想、分支限界法思想和贪心法思 想等。

枚举法思想的核心是使用深度优先策略编程。 枚举算法[22]的特点是算法简单。但是运算量非常大，随着结点的变大，求解循环数增大，

计算的速度会越来越慢。如果枚举范围非常广，在运行时间上就难以达到标准。求 TSP 问题 时，如果将顶点 1 设为起始点，接着求{2…N}的一个全排列，使路程 1→{2…N}的全部排列

→1 上所有的权值的和最小。所有可能解因为（2，3，4，…，N）的不同排列来决定。 为便于讨论，本文先对求解空间树结构方面的术语进行学习。下面介绍用解的空间树来

分析回溯法和分支限界法。问题状态（problem state）是由求解空间树种的节点所决定的。从 源点出发的全部路线一同决定此课题的状态空间（state space）。解状态（solution states）代表 树的跟到达题目状况 S 的路径确定求解空间中的元组。答案状态（answer states）代表树根到 课题状况的路径是否确定了课题的解。状态空间树（state space tree）等于解的空间的树结构。 对于旅行商问题，我们首先假设出状态空间树。然后能生成要解决问题的状态，然后能 确定上述要解决问题状态中的解。最后在这里面找到我们需要的解状态。最终解决上述问题。 有两种路径可以产生题目的状态。假设已经产生了一个结点，但子节点还没有完全生成，那 么称这个结点为活结点。如果一个活节点正在产生子节点，那么称它为 E-节点。相对地，死 结点就是不会再生成儿子结点（无论是满了还是不再生成了）的节点。有两种方法可以生成 问题状态，无论是什么方式，都需要知道活节点有哪些，而且都会使用限界函数去消灭还没 变成其儿子结点的活结点。要是 TSP 问题需求找出所有的解，那么要找到可能的答案的结点。文献综述

E-结点始终存在到无法使用状态的产生方法定义为分支限界法。 回溯法的思想[23]也可用于分析 TSP。 如果使用回溯法，那么所满足的解一定要能写成一个 n- 元组(x1,…,Xn)。其中 x1 是取自

某个有限个穷集 Si。一般需要求解的问题，是求解某个使某一规范函数 P(x1,…,Xn)取最大值 的向量。

分支限界法的思想[30]是分析 TSP 问题另一个重要手段。 贪心法[31]是也是一种能够分级别处理方法。经过了改进后，它首先旅行商问题描述。指

定一种度量标准。然后我们按这种规定对 n 个输入城市进行排序，然后一一输入。如果其中 的输入无法产生可行解，那么不标记这个城市。

想要用贪心法求得最优路径，算法应逐边地构造树。而且依据特殊的度量选择要被计入 的边。

1。2 遗传算法简介

遗传算法（Genetic Algorithm）是已达尔文生物进化论为基础，演化而来的。通过使用自 然选择和遗传学机理的生物进化过程来模拟求解的问题。是一种使用模拟自然进化过程的方 法来求解问题。能有效搜索最优解[24]。遗传算法是从所求问题中找到可能是所求解集作为独 立一个种群（population）进行运行。而一个种群则由经过基因（gene）编码。是由一定数目 的个体(inpidual)组成。其中每个个体是具有染色体的。并且染色体包括遗传物质。是所有 遗传物质的集合。所以，在计算之前就要将表现型和基因型对应匹配即编码工作。因为模仿 基因编码的工作难以实现，所以我们一般将其进行简化替换。来,自,优.尔:论;文*网www.youerw.com +QQ752018766- 一类多旅行商问题求解算法及分析(3):http://www.youerw.com/zidonghua/lunwen_88513.html