3

如何将旅行商问题的（决策版本）转换为哈密顿电路问题（即如何将 TSP 简化为 HCP，以便如果我有 HCP 的解决方案，那么我将使用该解决方案来解决 TSP 问题）？

4

6 回答 6

5

NP 中的每个问题都可以多项式时间简化为任何 NP 完全问题——这就是使 NP 完全问题如此重要的原因。

这是一个减少链：

  1. 顶点覆盖可以简化为哈密顿回路。
  2. 3-SAT 可以简化为 Vertex Cover。
  3. 可满足性可以降低到 3-SAT。
  4. NP 中的任何决策问题都可以简化为可满足性（Cook-Levin 定理）

TSP 是 NP 中的一个问题，因此可以在非常长的多项式时间内将其简化为哈密顿回路。

我从Computers and Intractability: A Guide to the Theory of NP-Completeness 中得到了简化

于 2012-11-14T06:28:34.553 回答
0

哈密​​顿循环问题被证明是 NP 完全的（截至今天，已知解决的最佳性能算法具有指数复杂度），

此外，哈密顿循环问题是一个决策问题（给定一个图，是否存在一个覆盖所有顶点的非重叠边的循环？）而 TSP 是一个搜索问题（在所有哈密顿循环中，给我一个较低的成本）。

所以....复杂性对于足够大的问题是不切实际的）。

如果您只想解决 TSP，则只需使用已知算法之一。其中一些被设计为在少数顶点上表现得相当好（这对你来说可能就足够了）。

注意：我假设您的意思是 TSP 搜索问题和哈密顿循环决策问题，情况可能并非如此。

于 2013-02-18T00:19:23.713 回答
0

拿你的图表并删除所有的边。取任意顶点 v 并从该顶点开始添加反向有向边，如果添加的边目标距离 v 不远，而不是 k 来自 tsp 决策问题的长度常数。

如果构建的图有一个哈密顿圈，那么它也是原始图中长度 < k 的环，因此是 TSP 的一种解决方案。

相反，如果图中没有哈密顿循环：因为您已经构建了从顶点 v 开始的所有长度 < k 的路径，并且作为 TSP 的解决方案，是从 v 开始的长度 < k 的路径和一个哈密顿循环，原始图中没有 TSP 的解决方案。

于 2017-09-24T19:38:36.457 回答
-1

从维基百科关于哈密顿路径问题的文章，可能会给你一个提示：

“哈密顿循环问题也是旅行商问题的一个特例，通过将两个城市之间的距离设置为如果它们相邻，则设置为 1，否则为 2，并验证行进的总距离等于 n（如果是，则路线是哈密顿回路；如果没有哈密顿回路，那么最短的路线会更长）。

于 2012-11-13T18:48:41.307 回答
-1

TSP 的输入实例是一个完全图，Ham_Cycle 的输入实例是一个无向图 G(u,v)。然后你的转换函数必须将图 G 映射到一个完整的图。

  • 在 G 的相同顶点上构造一个完全图 G'，权重为 fn w(u,v)
  • w(u,v) = 1 如果边 e(u,v) 在 G 中存在
  • w(u,v) = INF 否则
  • 将权重 k 设置为 |V| （六）
  • 在 G' 上运行 TSP 问题
于 2013-01-03T18:05:22.730 回答
-1

好吧，问题是你到底想做什么。通常，TSP 是关于寻找smallest方法的。如果你想找到最小的方法，那么你不能这样做。仅当您从汉密尔顿问题中获得所有解决方案时。
因为汉密尔顿问题不关心边权重，但对于推销员来说这是必要的。

示例：图 A、B、C 与 A-(10)-B、B-(10)-C、C-(1)-A

显然，A->B->C 是汉密尔顿方式，但 TSP 的最佳解决方案是 A->C->B

如果您只是想为 TSP 找到任何解决方案，不一定是最小的，那么您只需将 TSP 节点映射到 Hamilton 节点，解决它，返回映射就完成了。

于 2012-11-13T22:01:35.337 回答