完全带权图和哈密顿回路

Question

我在期中考试中遇到了一个问题。有人能解释一下答案吗？

问题A：给定一个完全加权图G，找到一条带有最小权重的哈密顿回路。

问题B：给定一个完全加权图G和实数R，G是否有一条带有最大权重为R的哈密顿回路？

假设有一台机器可以解决问题B。如果每次给出G和实数R来解决问题A，我们最多可以调用多少次B？假设G中边的总数为M。

1）我们无法做到这一点，因为存在不可数状态。

2）最多可以调用O(|E|)次。

3）最多可以调用O(lg m)次。

4）因为问题A是NP难问题，所以无法做到。

- user4559497

---

我猜想问题的答案应该是 2) O(|E|) 次，即先找到最优权重，再逐个尝试去掉每条边，以确定哪些边属于最优路径，但这个问题的构造很差。 - David Eisenstat

@amit 如果我们假设权重为整数，那么O(log M)就足以确定精确的最优解了，但是谁知道呢？信息理论上O(|E|)就足以确定精确的最优解，但我不确定实际算法会是什么样子。这比这个问题应得的思考更多了。 - David Eisenstat

@Codor，可能是错误的，但问题中没有给出。 - user4559497

@nini，NP或P在这里并不是问题，我们只关心是否能够通过多项式时间算法将A转换为B。 （3）似乎是一个有效的方法，正如Rontogiannis在他的答案中指出的那样。 - Pham Trung

这怎么是一个有效的stackoverflow问题？ - m_power

Answer 1

第一个算法

答案是(3) O(lg m) 次。你只需要在加权图中执行最小哈密顿回路的二分查找。注意，如果图中存在长度为L的哈密顿回路，则检查是否存在长度为L'（其中L'>L）的哈密顿回路没有意义，因为你只关心最小权重的哈密顿回路。因此，在算法的每一步中，你可以消除剩余可能的路径权重的一半。因此，你将不得不在计算机中调用B O(lg m)次，其中m代表完整图中所有边的总权重。

---

编辑：

第二个算法

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

---

注意：

我提出的第一个算法可能是不正确的，因为有些人指出你不能在不可数集合上应用二分查找。由于我们正在谈论实数，因此无法在范围[0-M]内应用二分查找。

- Rontogiannis Aristofanis

---

我们已经讨论过这个想法，它失败的原因是：（1）OP要求实际路径，而不仅仅是权重。（2）您不能保证找到实值（非整数）权重函数的精确成本。 - amit

请查看http://www.seas.gwu.edu/~ayoussef/cs212/npcomplete.html上的yes/no表述。 - user4559497

请查看以下网址，其中包含有关使用实数的TSP公式：http://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture22.html - user4559497

@nini 我添加了第二个算法，它具有完全非多项式复杂度，但使用机器 O（|E|） 次（答案为 (2)）。由于没有关于算法复杂度的限制，只有对机器调用次数的限制，我认为这是正确的。 - Rontogiannis Aristofanis

亲爱的@RontogiannisAristofanis，你在这里吗？ - user4559497

Answer 2

我认为正确的选项是1-你不能这样做。原因是你只能在可数集合上进行二分查找。

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

然而，你可以在Log(n)的时间内无限接近A的答案，但你不能找到确切的答案。(n是可数空间的大小）

- Shervin

---

确实有很好的观点; 但是我们可以假设选择了一些“合理”的边权编码。 - Codor

Answer 3

假设在图形编码中，权重被编码为表示非负整数的二进制字符串，并且问题B实际上可以通过输入实数并根据其执行计算来解决，那么事情显然如下。

可以在整数区间{0,...,M}上进行第一次二分查找，以在O(log M)次调用问题B算法的情况下获得哈密顿回路的最小权重。由于之后已知最佳解，我们可以消除G中的单个边，并使用生成的图作为问题B算法的输入，以测试最优解是否发生变化。该过程使用O(|E|)次调用问题B算法来识别出在最优哈密顿回路中出现的边。该方法的总运行时间为O((|E| + log M) * r(G))，其中r(G)表示将图G作为输入的问题B算法的运行时间。我认为r是一个多项式，尽管问题没有明确说明；总体而言，该方法的总运行时间在输入的编码长度上是多项式有界的，因为M可以在多项式时间内计算（因此在输入G的编码长度上是伪多项式有界的）。

话虽如此，所谓的答案可以如下评论。

1. 答案是错误的，因为必要状态集是有限的。
2. 可能是真的，但并不是从上面讨论的算法中得出的。
3. 可能是真的，但并不是从上面讨论的算法中得出的。
4. 答案是错误的。严格来说，问题A的NP-难度并不排除多项式时间算法；此外，问题B的算法未被说明为多项式，因此即使P=NP也不会成立，如果问题A可以通过对问题B的算法进行多项式次数的调用来解决（这是通过上述算法的情况）。

- Codor

---

4. 如果仅仅因为一个问题是NP难问题就认为它无法解决，那肯定是错误的。我在问题描述中也没有看到要求使用B来解决A，并且需要使用多项式时间算法的要求。

- TravisJ

请查看http://www.seas.gwu.edu/~ayoussef/cs212/npcomplete.html上的yes/no公式。 - user4559497