algorithm - 完全加权图G，求权值和一机

Question

我阅读了很多关于 Complete Weighted Graph and Hamiltonian Tour 的内容本站的一个用户提出的主题，问了我大学的很多教职员工，但得不到一个好的答案，我把这个问题的一个重要部分改成如下:

Problem A: Given a Complete Weighted Graph G, find weights of Hamiltonian Tour with minimum weight.

Problem B: Given a Complete Weighted Graph G and Real Number R, does G have a Hamiltonian Tour with weight at most R?

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

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

2. O(|E|) 次

3. O(lg m) 次

4. 因为 A 是 NP-Hard，所以这是不可能的。

我读了this file ，在第 2 页他写道:

a) optimization problem (in the strict sense): find an optimal solution

b) evaluation problem: determine the value of an optimal solution

c) bound problem: given a bound B, determine whether the value of an optimal solution is above or below B.

下两段

To exploit c) in solving b), we use the fact that the possible values of a combinatorial problem are usually discrete and can be taken to be integers. Assume we can solve the bound problem c) within time T. For the corresponding evaluation problem b) one usually knows a priori that the value lies within a certain range [L, U] of integers. Using binary search, we solve the evaluation problem with log | U - L | calls to the bound problem c), and hence in time T log | U - L |.

接下来他写道:

Ex: TSP on weighted graph Kn = (V, E, w: E -> Reals), |V| = n, |E| = n-choose-2. Use c) to solve b). A tour or Hamiltonian cycle in a graph of n vertices has exactly n edges. Thus, the sum S of the n longest edges is an upper bound for the length of the optimal tour. On the other hand, the sums of all m choose-n subsets of n edges is a finite set of numbers, and the minimal non-zero difference d among two of these numbers defines the granularity of the tour lengths. Two distinct tours either have the same value, or their lengths differ by at least d. Thus, a binary search that computes log( S / d) bound problems determines the length (value) of an optimal tour.

我的问题是，我们能否以这种方式调整此解决方案以选择 (3)？

Answer 1

Suppose there is a machine that solves B. How many times can we call B (each time G and Real number R are given),to solve problem A with that machine? Suppose the sum of Edges in G up to M.

O(log M)。

选择a = 0, b = M。

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

2. 结果是True

   那么有一个权重至多为 R 的哈密顿环路。有没有更严格的上限？设置 b = R 并重复找出答案(转到 1)。

3. 结果是False

   则不存在权重至多为R的哈密顿环:最小权重较大。设置 a = R 并重复(转到 1)。

这是 binary search algorithm .

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

例如，如果您的其中一条边的值为 pi，您将不得不接受它的近似值作为开始，因为数学常数 pi 具有无限多的数字。因此，无论您使用什么算法，都会遇到一定程度的精度问题。