TSP上界
考虑欧氏平面上的完全图 ,
此时边权为正且满足三角不等式. 设最优环游为 , 启发式算法产生的解记作 , 边权 .
最近邻法
从起点开始, 每次选择距离当前点最近的点即可. 满足 , 粗略点就是 .
如果图不满足三角不等式,
那么最近邻法产生的环游与最优环游的比值可以任意大.
插入法
Christofides 启发式方法
需要用到最小生成树 , 记 为 中度数为奇数的顶点的集合, 在 中, 由握手定理可得 为偶数, 于是必然有
为偶数, 因此诱导子图 存在最小费用完美匹配 , 令 ,
在这里边集的并要求保留重复元素, 即允许出现重边, 这样得到子图 , 显然 中所有点的度数均为偶数,
因为将完美匹配并入最小生成树
中时未改变偶数度顶点的度数, 给每个奇数度顶点的度数加上了一, 于是 中存在欧拉圈, 设欧拉圈为 ,
在欧拉圈的基础上构造TSP环游: 置 , 按照欧拉圈的顺序逐边向
中添加边, 若在 时
已经被访问过且 未被访问过,
则置 (即跳过已经被访问过的点),
直到所有顶点都被访问.
定理1 Christofides 启发式方法得到的环游满足 .
PROOF 由于环游 是在 上进行改进得到的,
只需要证明 即可, 分别考虑最小生成树和完美匹配的边权. 首先一定有
, 如若不然, 去掉
的一条边得到的生成树便可成为新的最小生成树; 对于 , 按照顶点在 的顺序将 中的点画成一个圈 , 由三角不等式可得 , 且圈 可以被划分为 的两个完美匹配 , 显然最小费用完美匹配 满足 . 因此 .
这个 不能再继续减小了.
还有一种更简单的用到最小生成树的启发式算法:
先序遍历最小生成树得到的环游可以作为一个启发式的解, 此时满足 .
-交换
常用的是2-opt和3-opt.
-opt用于改进已有的环游,
比如Chrisrofides产生的环游 . -opt 是对 的不相邻的两条边做交换操作, 更详细地说,
是将这两条边删去得到两条路径 , 通过一种唯一的方法将 组合成一条新的环游 , 若 , 那我们就认为 是更优的选择.
最终可以达到一个最优的状态, 即不能再通过2-交换得到更优的环游.
3-交换是类似的操作, 删边-重新组合. 当 时,
删边重新组合成新的环游的方法数呈指数级上升, 一般不采用.
遗憾的是虽然可以在
内验证一条环游是否是2-opt的,
但是有可能需要指数次交换才能将任意一条环游变为2-opt的.
Lin-Kernighan
Lin-Kernighan启发式方法简称为LKH,
是目前最高效的TSP启发式算法之一。
首先需要定义 -path相关的概念. -path是一条path满足path的终点是路径上的某个点,
也就是说 -path中含有一个圈,
如下图的 所示, 其中 为该路径的终点(当然也在路径中出现过),
为 紧跟着的点.
可以通过一个 -path
构造一个TSP环游, 构造规则为: 将路径终点所在的路径中的
LKH算法的核心思想就是不断通过删边与加边构造费用越来越小的 -path.
11
Animated Algorithms for the Traveling Salesman Problem
(stemlounge.com)
TSP下界
Held-Karp bound
对于任意一个环游 ,
一个相当 trivial 的下界可以由下面的方式找到:
对于 , 设 是以 为端点的两条不同的边, 令 , 那么就有 , 倘若有 那么 自然就是环游
费用的一个下界.
那么该如何找到这样的 呢?
是相当好找的, 找到费用最小的以
为端点的两条边即可. 对于 , 首先 是 的一棵生成树, 那么显然
的最小生成树的费用可以作为下界 ,
上面这样的 称为 1-tree
bound.
为何不直接用
的最小生成树的费用来作为下界呢? 上面的方法是否可以获得更紧的下界呢?
这个界还可以改善, 比如下面的例子中的 1-tree bound 是 , 这是一个相当平凡的值,
出现这种原因是因为有三条边权为
的点与点 相连,
这意味着这三条边在最小生成树中一定会出现, 为了改善这种情况,
可以考虑修改边权而不改变最优环游的位置(当然其实我们不关注修改后的最优环游,
关注的是修改后的 1-tree bound). 可以将以 为端点的边的权重都加 , 那么下界将变为 而最优环游并不发生变化.
下面形式化地叙述 Held-Karp bound 的计算过程:
定理1 (Held-Karp bound) 设原始费用函数为 , 对于任意 和
, 给顶点 分配一个实数 , 将以顶点 为顶点的边的费用都减少 , 得到一个新的费用函数为 (即对任意 ) ,
令 为 关于费用 的一个 1-tree bound, 那么 是 关于费用 的最优环游的费用的下界.
如何寻找合适的 ? Held
和 Karp 给出了一个迭代策略: 设 表示第 轮迭代赋予的值, 首先初始化 同时得到一棵初始的
1-tree bound 对应的子图 , 接着设
表示 中顶点 的度数, 那么 ,
其中实数 为一个固定的步长.
步长也可以做启发式的更改, 迭代公式可以写为 ,
其中 其中 是一个 TSP 上界,
可以由前述的启发式算法得到, 是当前的 Held-Karp
bound, 是一个在 的实数, 可以令 并使序列以固定的步长减少,
这个数取决于顶点数目以及我们愿意花费的时间.
可以证明固定步长的迭代会收敛到一个最优 Held-Karp 界对应的 ,
但这个收敛时间可能是指数级别的, 同时并不是每次迭代获得的 都改善当前的 Held-Karp 界,
可能会获得更糟糕的界.
可以使用线性规划获得与 Held-Karp bound 完全等价的bound.
线性规划下界技术
TSP的一个DP算法
设 ,
考虑到环游中起点的任意性, 以
为起点. 对非空集合 , 设 表示以 为起点 为终点且经过 中所有点的最短路径, 首先 时 ; 当
时, 只需枚举 的前置结点 , 此时终止于 的最短路径对应的 可以表示为 , 那么就有 最终最优环游为 . 这个动态规划的复杂度为
,
其中 为多项式.
