algorithm - 完全加权图和哈密顿之旅

Question

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

问题 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，所以这是不可能的。

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]

范围内应用二进制搜索