6 algorithm graph computation-theory hamiltonian-cycle np
我在这个网站上阅读了很多关于完整加权图和汉密尔顿旅游主题的内容,其中一位用户询问,询问我大学的很多工作人员,但无法得到一个好的答案,我将这个问题的一个重要部分更改为如下:
问题A:给出一个完整的加权图G,找到
weights最小权重的哈密顿游.问题B:给定一个完整的加权图G和实数R,G是否具有最多R的哈密顿巡回训练？
假设有一台机器可以解决B.我们可以多少次调用B(每次给出G和实数R),用该机器解决问题A？假设G中边缘的总和达到M.
我们不能这样做,因为有无数的状态.
O(| E |)次
O(lg m)次
因为A是NP-Hard,这是无法做到的.
我读了这个文件,在第2页他写道:
a)优化问题(严格意义上):找到最优解
b)评估问题:确定最优解的价值
c)绑定问题:给定绑定B,确定最优解的值是高于还是低于B.
在接下来的两段
为了在解决b)中利用c),我们使用这样的事实:组合问题的可能值通常是离散的并且可以被认为是整数.假设我们可以在时间T内解决约束问题c)对于相应的评估问题b)人们通常知道该值在整数的某个范围[L,U]内.使用二进制搜索,我们用log |来解决评估问题 U - L | 调用绑定问题c),因此在时间T log | U - L |.
在接下来他写道:
例如:加权图上的TSP Kn =(V,E,w:E - > Reals),| V | = n,| E | = n-choose-2.用c)解决b).n个顶点图中的巡回或哈密顿循环恰好有n个边.因此,n个最长边的和S是最佳巡回长度的上限.另一方面,n个边缘的所有m个选择n子集的和是一组有限数,并且这些数中的两个中的最小非零差d定义了巡回长度的粒度.两个不同的游览具有相同的值,或者它们的长度相差至少d.因此,计算log(S/d)约束问题的二进制搜索确定最佳游览的长度(值).
我的问题是我们可以通过这种方式调整这个解决方案来选择(3)吗？
假设有一台机器解决B问题。我们可以调用B多少次（每次给出G和实数R），用该机器解决问题A？假设 G 至 M 中的边之和。
O(log M)。
挑选a = 0, b = M。
放R = (a + b) / 2。以此解B。R
结果是True
然后是重量最大的哈密顿巡R。有没有更严格的上限？设置b = R并重复即可找出答案（转至 1）。
结果是False
那么就没有权重最大的哈密顿巡游R：最小权重更大。设置a = R并重复（转至 1）。
这就是二分查找算法。
虽然理论上该算法确实不适用于所有实数（尤其是无理数），但实际上不可能有无理数。无论如何，计算机只能表示无理数的近似值，因此您可以使用二分搜索来获得近似值，该近似值可以达到您愿意运行算法的小数位数。
例如，如果您的一条边的值为pi，那么您首先必须选择它的近似值，因为数学常数pi具有无限位数。因此，无论您使用哪种算法，都会遇到一定程度的精度问题。