给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路，这样的问题被称作旅行商问题（Travelling salesman problem, TSP），又叫货郎问题、推销员问题 等等。

该问题是组合优化中的一个NP难问题，在运筹学和理论计算机科学中非常重要。

除了经典TSP（CTSP）问题外，它还有一系列变种问题，包括但不限于不对称的TSP（ATSP）、可重复 TSP、多人TSP（MTSP）等等。

本文章皆在记录我在学习算法过程中，收集和解决的各类TSP问题，持续更新中（大概）。

CTSP

对于给定的城市集合 $C=\{c_1,c_2,...,c_n\}$ ，已知相互连通的两个城市间的距离有：

$d(c_i,c_j)=d(c_j,c_i)$

TSP 问题就是寻找一种路径，使得该路径经过 $C$ 中所有的城市且仅一次并最终回到起点，且路径最短。
TSP 问题一种解的空间可表示为 $K=<k_1,k_2,...,k_{n-1},k_n>$ 表示对集合 $C$ 的一种排列，则最优解则是使得下式成立的一种排列：

$\min\sum_{i=1}^{n-1}d(k_i,k_{i+1})+d(k_{n},k_1)$

我们可以用完全无向图 $G(V,E,W)$ 对该问题进行抽象。其中， $V$ 就是无向图的点集， $E=\{(v_i,v_j)|1\leq i,j\leq n\}$ 是无向图的边集，而 $W$ 则是边的权重，物理意义是两个城市间的距离。

TSP 问题就是对于该完全无向图求出使得边权之和最小的 哈密顿回路|Hamilton Cycle。

回溯+分支定界

回溯算法主要是基于 DFS 或 BFS 对解空间进行搜索的一种算法，本质上也是一种穷举。将其作用于 CTSP 问题，我们可以构建一棵 解空间树，此处则是 排列树 来进行求解。如下图所示：

图示给出的是结点数为 4 时，固定结点 1 对剩下的结点进行全排列的结果。可见，排列树的叶子结点个数会随着规模的增加而成指数上升。

对于本问题来说，利用深度优先搜索是一个较直观的搜索策略。为了进行剪枝从而排除一些不必要的计算以加快计算效率，我们可以在 DFS 的基础上利用 分支定界（Branch & Bound）的思想，设计 代价函数 剪枝。

当搜索完成了前 $j$ 步时，排列树此时已导出解为 $K_j=<k_1,k_2,...,k_j>$ ，则当前的路径长为： $\begin{aligned}L'=\sum_{i=1}^{j-1}d(k_i,k_{i+1})\end{aligned}$ . 此时还剩下 $K-K_j=<k_{j+1}..k_n>$ 这系列结点没有经过。
那么最终路径长度存在一个很明显的下界，该下界由 $L'$ 与剩余所有结点的最小边权之和共同组成。

这是因为，与任意结点 $k_m\in K-K_j$ 相连的边权大小一定不超过与该点相连的最小边。所以每一个剩余结点的最小边之和自然组成了剩余 $n-j$ 步搜索结果的下界。
即：

$L_{-}=L'+\sum_{i=j}^n\min_{k_m\in K-\{k_i\}}d(k_i,k_m)$

以下图为例，假设当前这个搜索分支导出了一个子解 $<1,3,2>$ ，与端点 (2) 相连的最短边长度是 2，与端点 (4) 相连的最短边长度是 2。所以最终得到下界路径长为 26.

我们就以该下界作为代价函数，进行剪枝：

完全搜索其中一个分支（解），得到该分支下的路径长，记为 $Lmin$ ；
回溯搜索下一个分支，在结点处计算此时的代价函数 $L$ ；
如果 $L\gt Lmin$ 说明在该分支下最理想的情况得到的解也不可能低于 $Lmin$ ，则放弃该分支，转到 (2) ；
如果 $L<Lmin$ 则继续遍历该分支的下一个结点，然后计算此时的代价函数 $L$ ，继续判断是放弃分支还是继续遍历。如果该分支搜索结束后仍有 $L<Lmin$ 则更新 $Lmin\leftarrow L$ ，转到 (2)；
直到所以分支均讨论完毕则算法结束。

用 $vis[1..n]$ 对结点的访问进行标记记录，以实现回溯。
用 $step$ 表示当前分支的第 $step$ 个结点标号。
用 $d[1..n,1..n]$ 存储两两结点间的距离，其中规定 $d[i,i]=\infty$ 。
用 $path[1..n]$ 存储当前分支的解。
用 $Lmin$ 存储 TSP 问题的最短路径值，初始化 $Lmin\leftarrow +\infty$ 。
用 $L$ 存储当前子解中已走过的路径长，即为上面我们推导时出现的 $L'$ 。

算法伪码：

$\begin{aligned} &\text{Algorithm: }\;\text{TSP-DFS}(L,step)\\\\ 1.&\;\mathbf{if}\;step=n\;\mathbf{then}\\ 2.&\;\qquad Lmin\leftarrow \min(Lmin, L+d[step,1])\\ 3.&\;\mathbf{else}\\ 4.&\;\qquad sum\leftarrow \text{cost}(step)\;//\text{计算代价}\\ 5.&\;\qquad \mathbf{if}\;L+sum\gt Lmin\;\mathbf{then}\\ 6.&\;\qquad\qquad \mathbf{return}\;//\text{剪枝}\\ 7.&\;\qquad \mathbf{for}\;i=2\;\mathbf{to}\;n\;\mathbf{do}\\ 8.&\;\qquad\qquad vis[i]\leftarrow1\\ 9.&\;\qquad\qquad path[step]\leftarrow i\\ 10.&\;\qquad\qquad \text{TSP-DFS}(L+d(path[step-1],path[step]),step+1)\;//\text{访问下一个结点}\\ 11.&\;\qquad\qquad vis[i]\leftarrow0\;//\text{回溯}\\ 12.&\;\mathbf{return} \end{aligned}$

注：上述伪码中，第 4 行的 cost() 函数是根据 step 计算剩余结点的最短边之和，可用下面的数学式表达：
$cost(step)=\left\{\sum_{vis[i]=0}\min_{1\leq j\leq n,j\neq i} d[i,j]\right\}+\min_{1\leq j\leq n,j\neq step} d[step,j]$

不难得出，在固定起点后，排列树的叶子结点树在 $O((n-1)!)$ ，每一个分支的每一个结点都需要进行 $O(1)$ 的代价函数计算，一共 $n$ 个结点，因此该算法在最坏情况下的时间复杂度为 $O(n!)$ .
由于需要对解空间进行保存，对结点的访问情况进行标记，所以空间复杂度为 $O(n)$ .

算法的具体 c 系列语言实现如下：

#include <iostream>
#include <string.h>
#include <cstdlib>
using namespace std;
int n = 4; // 结点个数
int d[4][4] = {{INT32_MAX, 5, 9, 4},
			   {5, INT32_MAX, 13, 2},
			   {9, 13, INT32_MAX, 7},
			   {4, 2, 7, INT32_MAX}};// 距离矩阵
int visited[4] = {0}; // 标记数组
int path[4] = {0}; // TSP路线
int Lmin = INT32_MAX; // 当前最小代价

// 计算理想的最小多余代价
int mincost(int step){
	int sum = 0, tmp;
	for(int i = 1; i < n; i++){
		tmp = INT32_MAX;
		if(visited[i] == 0){
			for(int j = 0; j < n; j++){
				tmp = min(tmp,d[i][j]);
			}
			sum += tmp;
		}
	}
	tmp = INT32_MAX;
	for(int j = 0; j < n; j++){
		tmp = min(tmp,d[path[step-1]][j]);
	}
	sum += tmp;
	return sum;
}

void dfs(int L, int step){
	if(step == n){ //一个分支搜索结束
		cout << "paths: " << endl;
		for(int i = 0; i < n; i++){
			cout << path[i]+1 << " ";
		}
		L += d[path[step-1]][0];
		if(L < Lmin) Lmin = L; //更新最优解
		cout << "Length: " << L << endl << endl;
		return;
	}
	int sum = mincost(step);
	if(L+sum > Lmin){
		cout << "CUT OVER" << endl << endl;
		return; //根据代价函数剪枝
	}
	for(int i = 1; i < n; i++){
		if(visited[i] == 0){
			visited[i] = 1; //标记访问
			path[step] = i; // 扩充解
			dfs(L+d[path[step-1]][path[step]], step+1); //访问下一个结点
			visited[i] = 0; //回溯
		}
	}
}

int main(void){
	visited[0] = 1; path[0] = 0; //固定第一个结点
	dfs(0, 1);
	cout << endl << "min Length = " << Lmin;
    return 1;
}

运行结果如下：

paths:
1 2 3 4 Length: 29

paths:
1 2 4 3 Length: 23

CUT OVER

paths:
1 3 4 2 Length: 23

paths:
1 4 2 3 Length: 28

paths:
1 4 3 2 Length: 29


min Length = 23