一旦知道最短路线的距离，就可以解决旅行推销员问题

Question

我正在尝试解决 TSP (Travelling Salesman Problem)，但不是以传统方式。我正在按照这些步骤操作。

1) First I change the TSP to a true / false problem.

现在这个问题的定义是："Is there a route by all the cities with a total distance less or equals than k?" 假设我有一个算法 TSP_tf(k) 来解决它。

2) Then I search the minimum k.

这个是，我搜索"which is the distance of the shortest possible route"。

解决它的有效算法是使用二分法搜索。我从 k=1 开始，然后调用 TSP_tf(k)。如果它 returns 为假，我将 k 乘以 2，并继续调用 TSP_tf 直到返回真。发生这种情况时，搜索区间 (k/2 - k] 中 returns 为真的最小值 k，也使用二分法搜索。

然后我会得到最小距离min_k。

3) Return the shortest route of the TSP knowing its distance is min_k.

这就是我的问题所在。如何解决这个问题的有效算法？我所说的高效是指一种好的方法 :) 很明显 TSP 仍将是 NP。

Answer 1

你的TSP_tf就是通常所说的决策问题版本。该问题是 NP 完全问题，请参阅 https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computational_complexity 进行验证。所以你不应该希望它会很容易处理。

也就是说，同一篇维基百科文章提供了大量信息，介绍了在实践中解决 TSP 问题的惊人有效方法。

Answer 2

我终于解决了。

假设我们有一个图表 g，它表示 TSP 的城市及其连接。一个节点代表一个城市，一个加权边代表两个城市之间有连接，其权重对应的距离。

为了得到给定距离的最短路线，让我们一一删除边，看看它们是否是最短路线的一部分。我们怎么知道呢？如果我们从图中删除一条边 e 并用已知的最短距离 min_k 调用 TSP_tf，可能会发生两件事：

TSP_tf(min_k) == false。也就是说，删除e使得无法获得min_k距离的路线。 e是最短路线的一部分。
TSP_tf(min_k) == true。在没有连接 e 的情况下，仍然可以获得具有相同最小 min_k 距离的路线。 e不走最短路线

如果我们逐步将它应用到图的所有边上，我们可以获得准确的最短路线（或者更好地说，最短路线之一，因为可能有不止一种解决方案）。

// min_k is the distance of the shortest path of the TSP represented by the graph g.
Graph TSP(Graph g, int min_k)
    Graph shortestPath = g;
    For (Edge e in g)
        // Delete the edge e.
        shortestPath -= e;
        // e is part of the shortest path.
        If (TSP_tf(shortestPath, min_k) == false)
            shortestPath += e;
        EndIf
    EndFor
    Return shortestPath;
EndTSP

我们知道，图的最大节点数是1/2 * |V| * |V-1|，即|V|个节点数。每个节点调用TSP_tf次，所以调用TSP_tf的次数有一个峰值O(|V|^2)，是一个高效的算法。

一旦知道最短路线的距离，就可以解决旅行推销员问题

Solve Travelling Salesman once you know the distance of the shortest possible route

algorithm

traveling-salesman

np