将TSP简化为哈密顿电路

我如何将旅行推销员问题的(决策版本)转换为哈密顿电路问题(即如何将TSP简化为HCP，以便如果我有HCP的解，那么我将使用该解来解决TSP问题)？

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

以下是一系列削减：

TSP是NP中的一个问题，因此它可以在长得离谱的多项式时间内简化为哈密顿电路。

我从计算机和难处理性中得到了约简：NP完全性理论指南

哈密顿循环问题被证明是NP完全的(截至目前，已知求解性能最好的算法具有指数复杂性)，

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

所以。。。。我不认为你所要求的约简存在(直觉上TSP更复杂)，如果存在，我认为这对你没有帮助，因为哈密顿问题是NP完全的(指数复杂性对于足够大的问题来说是不切实际的)。

如果你只想解决TSP，那么只需使用已知的算法之一。它们中的一些被设计为对少数顶点表现相当好(这可能对您来说已经足够了)。

注意：我假设你指的是TSP搜索问题和Hamiltonian循环决策问题，但事实可能并非如此。

获取图形并移除所有边。取任意顶点v，并从该顶点开始添加反向边，如果添加的边目的地距离v不远于tsp决策问题的长度常数k。

如果构造的图具有哈密顿循环，那么它也是长度<k，从而得到TSP的一个解。

相反，如果图中不存在哈密尔顿循环：因为你已经构建了长度<k是长度<k，和一个哈密尔顿循环，在原始图中没有TSP的解。

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

"哈密尔顿循环问题也是旅行推销员问题的一个特例，通过将两个城市之间的距离设置为1(如果它们相邻)和2(否则)，并验证旅行的总距离等于n(如果是，则路线是哈密尔顿回路；如果没有哈密尔顿回路，则最短路线将更长)。">

问题是你到底想做什么。通常，TSP是关于找到smallest方式。如果你想找到最小的方法，那么你不能用这种方法。只有当你有汉密尔顿问题的全部解决方案
因为Hamilton问题不关心边权重，而是对于销售人员来说是必要的。

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

显然，A->B->C是Hamilton方法，但TSP的最优解是A->C->B-

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

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

相关内容