7

我在期中考试时遇到了一个问题。任何人都可以澄清答案吗？

问题 A：给定一个完整的加权图 G，找到一个具有最小权重的哈密顿环。

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

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

1）我们不能这样做，因为有不可数的状态。

2) O(|E|) 次

3) O(lg m) 次

4) 因为 A 是 NP-Hard 的，所以这是做不到的。

4

3 回答 3

3

第一种算法

答案是(3) O(lg m) times。您只需对加权图中的最小哈密顿之旅执行二分搜索。请注意，如果图中存在长度为 的哈密顿巡回，L则检查是否存在长度为 的哈密顿巡回是没有意义的，因为您对最小权重的哈密顿巡回感兴趣。因此，在算法的每个步骤中，您都可以消除剩余可能的游览权重的一半。因此，您将不得不调用您的机器时间，其中代表完整图中所有边的总权重。L'L' > LBO(lg m)m

编辑：

第二种算法

我对使用机器时间的上述算法进行了轻微修改O(|E|)，因为有些人说我们不能在不可数的可能值集中应用二进制搜索（它们可能是正确的）：从图中获取每个可能的边子集，并且对于每个子集存储一个值，该值是子集中所有边的权重之和。让我们将所有子集的值存储在一个名为 的数组中Val。这个数组的大小是2^|E|。按升序排序Val，然后对最小哈密顿路径应用二进制搜索，但这次调用仅使用Val数组中的值解决问题 B 的机器。由于每个边的子集都包含在排序数组中，因此可以保证找到解决方案。机器的总调用次数为O(lg(2^|E|))，即O(|E|)。所以，正确的选择是(2) O(|E|) times。

笔记：

我提出的第一个算法可能是不正确的，因为有些人指出您不能在不可数集中应用二进制搜索。由于我们谈论的是实数，我们不能在范围内应用二进制搜索[0-M]

于 2015-03-02T18:22:17.193 回答
1

我相信本应作为答案的选择是 1- 你不能那样做。原因是你只能对可数集进行二分查找。

请注意，图的边缘甚至可能具有负权重，此外，它们可能具有分数，甚至是不合理的权重。在这种情况下，答案的搜索空间将是所有小于 m 的实数值的集合。

但是，您可能在 Log(n) 时间内任意接近 A 的答案，但您找不到确切的答案。（n 是可数空间的大小）。

于 2015-02-20T16:21:10.887 回答
1

假设在图的编码中，权重被编码为表示非负整数的二进制字符串，Problem B并且实际上可以通过输入一个实数并在此基础上执行计算来通过算法求解，事情显然如下。

可以在积分区间上进行第一次二进制搜索，以获得在调用算法时{0,...,M}哈密顿环的最小权重。由于之后已知最优值，我们可以消除单个边并将结果图用作算法的输入，以测试最优值是否发生变化。此过程使用对算法的调用来识别出现在最佳哈密顿游程中的边。该方法的总运行时间为，其中表示以图为输入的算法的运行时间。我想O(log M)Problem BGProblem BO(|E|)Problem BO( (|E| + log M ) * r(G))r(G)Problem BGr是多项式，尽管问题没有明确说明这一点；总而言之，总运行时间将在输入的编码长度中以多项式为界，这M可以在多项式时间中计算（因此在输入的编码长度中是伪多项式的G）。

话虽如此，假设的答案可以评论如下。

  1. 答案是错误的，因为必要状态的集合是有限的。
  2. 可能是真的，但不遵循上面讨论的算法。
  3. 可能是真的，但不遵循上面讨论的算法。
  4. 答案是错误的。严格来说，NP -hardnessProblem A不排除多项式时间算法；此外，算法没有被Problem B声明为多项式，因此即使可以通过调用算法的多项式次数来求解（上面概述的算法就是这种情况）。P=NPProblem AProblem B
于 2015-02-24T15:36:54.263 回答