Travelling salesman problems

介绍

旅行商问题是组合优化领域中的一个经典问题，其目标是在给定路径集合中找到最短路径， 使得从一端出发，所有端点恰好经过一次后返回出发点。

Table of least distance

Table of least distance怎么列呢？

看图，得出距离。部分城市没有直接连接，那么可以使用最短路径算法计算端点之间最短距离。

图不复杂的话数学考试就瞪眼法吧

	A	B	C	D	E
A	-	11	13	11+8=19	13+18=31
B	11	-	24	8	14+8=22
C	13	11+13=24	-	32	18
D	19	8	32	-	14
E	31	22	18	14	-

Upper Bound & Lower Bound

Upper Bound

那么upper bound怎么找呢？

思路：

1. 把minimum spanning tree画出来，确保所有端点都包含在里面
2. 算一下MST的weight, 乘二 <—Initial upper bound
3. 寻找“shortcuts”, 用来消除重复访问， 形成一个有效的Hamiltonian Circuit

Shortcut

我们double完MST之后，可能会重复访问一些节点

那么我们要使用shortcut来跳过这些重复访问的节点， 使路径成为一个有效的TSP回路

需要移除重复访问的节点，当遇到已经访问过的节点时，直接跳过它，形成新的路径。

Nearest Neighbour Algorithm

步骤：

1. 选择起点

   • 任意一点， 除非题目规定

2. 选择最近的未访问节点

   • 选择weight最小的边
   • 如果有多个相等的最小边，随便选一个

3. 重复1-2步， 直到所有点被访问

Lower Bound

注意：只对classical problem有效

MST法：

步骤：

1. 移除一个端点V和与之相连的边

2. 找到移除端点V后图的Minimum Spanning Tree, 这个tree被叫做Residual Minimum Spanning Tree

3. 寻找连接端点V的两条最短边

   • 找到V连接回RMST的两条最短边
   • 计算这两条边的总weight

4. 计算lower bound

   • TSP Lower Bound = RMST weight + 这两条边的weight和

5. 对所有端点重复1-4步， 取最大值作为最终的lower bound

   • 但是考试会告诉你删哪个端点， 就不用这一步了

– 未完待续 –