6

我在这个网站上阅读了很多关于完整加权图和哈密顿之旅主题的内容，这些主题是由一位用户提出的，问了我大学的很多工作人员，但无法得到一个好的答案，我将这个问题的一个重要部分更改为如下：

问题 A：给定一个完整的加权图 G，找到weights具有最小权重的 Hamiltonian Tour。

问题 B：给定一个完整的加权图 G 和实数 R，G 是否有一个权重最多为 R 的哈密顿游程？

假设有一台解决 B 的机器。我们可以调用 B 多少次（每次给定 G 和实数 R）来用这台机器解决问题 A？假设 G 中的边的总和到 M。

  1. 我们不能这样做，因为存在不可数状态。

  2. O(|E|) 次

  3. O(lg m) 次

  4. 因为 A 是 NP-Hard，这是无法做到的。

我读了这个文件，在第 2 页他写道：

a) 优化问题（严格意义上）：找到最优解

b) 评估问题：确定最优解的值

c) 有界问题：给定一个有界 B，确定最优解的值是高于还是低于 B。

在接下来的两段

为了利用 c) 解决 b)，我们使用组合问题的可能值通常是离散的并且可以被视为整数的事实。假设我们可以在时间 T 内解决有界问题 c)。对于相应的评估问题 b)，人们通常先验地知道该值位于整数的某个范围 [L，U] 内。使用二分查找，我们用 log | 解决了评估问题。U - L | 调用有界问题 c)，因此在时间 T log | U - L |。

接下来他写道：

例如：加权图上的 TSP Kn = (V, E, w: E -> Reals), |V| = n, |E| = n-选择-2。使用 c) 解决 b)。n 个顶点的图中的环或哈密顿循环恰好有 n 条边。因此，n 条最长边的总和 S 是最优路径长度的上限。另一方面，n 条边的所有 m 个选择-n 个子集的总和是一组有限的数字，其中两个数字之间的最小非零差 d 定义了旅行长度的粒度。两个不同的旅行要么具有相同的价值，要么它们的长度至少相差 d。因此，计算 log(S / d) 界限问题的二分搜索确定了最佳游览的长度（值）。

我的问题是我们可以调整这个解决方案来以这种方式选择（3）吗？

4

1 回答 1

1

假设有一台解决 B 的机器。我们可以调用 B 多少次（每次给定 G 和实数 R）来用这台机器解决问题 A？假设 G 中的边的总和到 M。

O(log M).

挑选a = 0, b = M。

  1. 设置R = (a + b) / 2。用这个解决B。R

  2. 结果是True

    然后有一个至多有重量的哈密顿环R。有没有更严格的上限？设置b = R并重复找出（转到 1）。

  3. 结果是False

    那么没有最大权重的哈密顿巡回赛R：最小权重更大。设置a = R并重复（转到 1）。

这就是二分搜索算法。

虽然理论上该算法不适用于所有实数（尤其是无理数），但在实践中您不能使用无理数。无论如何，计算机只能表示无理数的近似值，因此您可以使用二进制搜索来获得一个近似值，该近似值适用于您愿意运行算法的尽可能多的小数。

例如，如果您的一条边的值为pi，则您必须从一开始就接受它的近似值，因为数学常数pi具有无限位数。所以无论你使用什么算法，你都会遇到一定程度的精度问题。

于 2015-03-15T19:10:36.117 回答