时间戳

首页 > 解决方案 > 证明 HAM-CYCLE 到 TSP 的减少是多项式时间的？

algorithm - 证明 HAM-CYCLE 到 TSP 的减少是多项式时间的？

问题描述

这是我们教授昨天上传的一道题，为明天的考试做准备。我的问题是b部分（下面用黑体字表示）；我不确定我应该做什么。

旅行推销员问题由一个推销员和一组城市组成。推销员必须从某个城市（例如家乡）开始访问每个城市，然后返回同一个城市。问题的挑战在于旅行推销员想要最小化旅行的总长度。

TSP = {(G, f, t): G = (V, E) 一个完全图，f 是一个函数 V×V → Z，t ∈ Z，G 是一个包含旅行商旅行的图，其成本为不超过 t}。

让 HAM-CYCLE 问题定义如下：给定一个无向图 G = (V, E)，是否存在一个包含 V 中所有节点的简单循环 H。

让一个完整的图是一个图，其中每个可能的顶点元组“之间”都有一条边。

a-为 TSP 定义证书。证明我们可以在确定性多项式时间内验证证书。

b-证明 HAM-CYCLE 到 TSP 的减少是多项式时间的。

c-使用 HAM-CYCLE 是 NP-完全的事实，我们可以得出什么结论？

标签： algorithmtraveling-salesmannpnp-complete

解决方案

正如您所介绍的那样，TSP 和 HAM-CYCLE 之间只有三个区别：

  • TSP 假设一个完整的图，而 HAM-CYCLE 允许一些顶点对不共享一条边。
  • TSP 为每条边分配一个成本，而 HAM-CYCLE 将所有边视为等价的。
  • TSP 寻求成本低于t的游览，而 HAM-CYCLE 接受任何游览。

给定一个图G和一个求解 TSP 的算法，我们可以如下求解 HAM-CYCLE：

  • 构造一个与 G 具有相同顶点集的完整图G '。
  • 当两个顶点在G中相邻时，让f （我们的 TSP 成本函数）返回 0 ，而当它们不相邻时返回 1。
  • 将我们的 TSP 求解算法应用于 ( G ′, f , t = 0)，并返回结果。这将发现是否存在仅使用 G 中存在对应边的 G ′的游览。

以上是从 HAM-CYCLE 到 TSP 的多项式时间缩减。（你明白为什么吗？）

推荐阅读