Question

算法: TSP 问题

Answer 1

TSP (Traveling Salesman Problem) 问题是一个经典的最短路径问题，它和我们平时看到的最短路径不同点是最短路径还包含了回来的路径。如下图，如果从节点1 开始也要在节点 1 结束。

这一个小小的回程问题使得整个问题都变复杂了，我们熟悉的 Dijkstra 不能用，要说某个点到所有点距离最小好像和最小生成树 (MST) 有关，但是计算回来的路径使得 MST 也不能用。

到目前为止还没有一个最优的解决方案，都是一些趋于最优的解决方案。

这个问题有很多应用场景：

为什么说是现有的解决方案呢？因为这个问题还没有找到最优的解，都是趋于最优的解。判断这趋于最优的方法我们一般使用一个比率来做。

目前已有算法的最优比率是 2/1，3/2，123/122，这里是越趋于 1 越好。

2/1 的这个算法主要使用了最小生成树，将最小生成树的总权重 * 2 就是 TSP 问题的答案。这个算法很容易理解，要经过所有的点还要路径小的 MST 能满足开始节点去往每个节点的最小距离，而要计算回来的路程，所以要将 MST Double 一下，这个 Double 就是回来的距离。

最优的比率计算如下：

这个算法还是以上面算法为基础，不过它没那么傻将 MST 双倍。而是对于那呢入度为奇数的节点连一个捷径。