解决旅行推销员一旦你知道最短路线的距离

我想解决TSP (Travelling Salesman Problem)，但不是以传统的方式。我正在执行这些步骤。解决旅行推销员一旦你知道最短路线的距离

1）首先，我改变TSP到真/假问题。

现在这个问题的定义是：“所有城市的总路程是否小于或等于k？假设我有一个算法TSP_tf(k)来解决它。

2）然后我查询的最小ķ。

这是，我搜索“哪个是最短路线的距离”。

一个有效的算法来解决它将与二分搜索。我从k=1开始，我打电话TSP_tf(k)。如果它返回false，我将k乘以2，并且一直呼叫TSP_tf，直到返回true。发生这种情况时，搜索最小k，在区间(k/2 - k]中返回true，并使用二分搜索进行搜索。

我会得到那么最小距离min_k。

3）返回TSP的最短路线知道其距离为min_k。

这里是我的问题来了。如何解决这个问题是一个有效的算法？通过高效率我的意思是一个好方法:)很明显，TSP将仍然是NP。

来源

2016-09-27 Santiago Gil

我认为这对我们来说有点过于宽泛。也许[cs.se]会愿意接受这一点，但即使他们可能想要一些更具体的开始。我不确定你的目标实际上是什么，因为所有三个步骤都是（我认为）NP。 – Teepeemm

将'min_k'提供给ILP模型将允许您修剪很多，但详细解释该方法需要整本书。 – harold

我投票结束这个问题作为题外话，因为它是关于计算机科学，不适用于编程。 [已转载到计算机科学]（http://cs.stackexchange.com/q/64037）。（将来，[请不要这样做]（http://meta.stackexchange.com/q/64068），[flag]（http://stackoverflow.com/help/privileges/flag-posts）您的问题请求迁移。） – Gilles

我终于设法解决它。

假设我们有一个图表g，它代表了城市及其TSP的连线。一个节点代表一个城市，一个加权边缘表示两个城市之间存在一个连接，并与其相应的距离有关。

为了在给定距离的情况下获得最短路线，我们删除一对一的边，并查看它们是否是最短路线的一部分。我们怎么能知道它？如果我们删除图中的边e我们称之为TSP_tf与已知的最短距离min_k，有两种情况：

TSP_tf(min_k) == false。这是，删除e使得无法获得与min_k距离的路线。 e是最短路线的一部分。
TSP_tf(min_k) == true。如果没有连接e，仍然可以获得具有相同最小距离的路线。 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的呼叫的数量具有峰值O(|V|^2)，这是高效的算法。

来源

2016-10-14 18:05:36

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

也就是说，同样的维基百科文章有大量关于在实践中解决TSP问题的惊人有效方法的信息。

来源

2016-09-27 21:13:41 btilly

是的我知道这个术语，但用我的语言，而不是英文。感谢您的链接，听起来很有趣，但是现在我想用这种方式解决问题，只是为了好奇。 –

解决旅行推销员一旦你知道最短路线的距离

回答

相关问题