当前没有测试数据。

著名的旅行商问题（Traveling Salesman Problem，TSP）指一个 旅行商从一个城市出发，经过每个城市一次且只有一次回到原来的地 方，要求经过的距离最短。TSP问题是一个NP难题，目前没有多项式时 间的高效算法。若采用搜索+剪枝，则该算法的时间复杂度为$O (n !)$， 数据量大时，这种方法无法解决，可以尝试采用动态规划解决。

假设已访问的节点集合为$S$（将源点$0$当作未被访问的节点，因为 从$0$出发，所以要回到$0$），当前所在的节点为$u$ 。

状态表示：$dp[S ][u ]$表示已经访问的节点集合为$S$，从$u$ 出发 走完所有剩余节点回到源点的最短距离。

状态转移方程： 若当前$u$ 的邻接点$v$ 未访问，则$dp[S ][u ]$由两 部分组成，第$1$部分是$u$到$v$ 的边值，第$2$部分是从$v$ 出发走完所有剩余 节点再回到源点的最短距离。访问完v 之后，已访问的节点集合变为$S$ $∪\{v \}$，若$u$ 有多个未被访问的邻接点$v$ ，则取最小值。$dp[S ][u]$=$min\{dp[S ∪${$v$ }$][v ]+$$d[u ][v ]|v ∉S$ }，如下图所示。

临界条件： $dp[(1<<n )-1][0]=0$，表示若所有节点都已被访问， 则此时已经没有剩余节点，从$0$节点出发走完所有剩余节点回到源点的 最短距离为$0$。

旅行商问题可以采用递推和记忆化递归两种方法求解。

来源

Traveling Salesman Problem，TSP