我在这个网站上读了很多关于Complete Weighted Graph and Hamiltonian Tour的话题,其中一个用户问了很多,问了我所在大学的很多工作人员,但都没有得到一个好的答案,我把这个问题的一个重要部分改为:
问题a:给定一个完整的加权图g,找到
最小重量的哈密顿游程。
问题B:给定一个完全加权图G和实数R,G
有一个重量不超过r的哈密顿巡演吗?
假设有一台机器解B,我们可以调用B多少次(每次给G和实数R),用它来解A问题?假设边的和在g到m之间。
我们不能这样做,因为有不可数的状态。
o(e)次
O(lg m)次
因为a是np难的,所以这是做不到的。
我看到他在第2页写道:
a)优化问题(严格意义上):找到一个
解决方案
b)评价问题:确定最优解的值
c)边界问题:给定一个边界b,确定
最优解大于或小于b。
下两段
为了利用c)解b),我们使用了以下事实
一个组合问题通常是离散的
整数。假设我们可以在时间t内解决边界问题c)。
相应的评估问题b)通常知道先验知识
这个值在整数的某个范围内。使用
二元搜索,用log u-l解决评价问题|
调用绑定问题c),因此在时间t log u-l。
接下来他写道:
例:加权图上的tsp kn=(v,e,w:e->实数),v=n,e|=
n-选择-2。用c)解b)。图中的圈或哈密顿圈
n个顶点中正好有n个边。因此,n个最长的和s
边是最佳巡更长度的上界。上
另一方面,n个边的m选择n子集的和是有限的
一组数,其中两个数之间的最小非零差d
这些数字定义巡更长度的粒度。二
不同的旅游线路要么具有相同的价值,要么其长度因
因此,计算对数(s/d)界的二进制搜索
问题决定了最佳旅游的长度(价值)。
我的问题是,我们能用这种方法调整这个解决方案来选择(3)吗?
最佳答案
假设有一台机器解B,我们可以调用B多少次(每次给G和实数R),用它来解A问题?假设边的和在g到m之间。
O(log M)。
选择a = 0, b = M。
设置R = (a + b) / 2。用这个R解b。
结果是True
然后有一个哈密顿巡游,其重量最多R。有一个更紧的上限吗?设置b = R并重复以查找(转到1)。
结果是False
则不存在重量最大的哈密顿游程:最小重量较大。设置R并重复(转到1)。
这是binary search algorithm。
虽然在理论上这种算法不适用于所有实数(特别是无理数),但在实践中不可能有无理数。计算机只能代表无理数的近似值,所以你可以使用二进制搜索得到一个近似于你愿意运行的算法的小数位数。
例如,如果你的边中有一个值“cc>”,那么你就必须先对它进行近似,因为数学常量有无限数量的数字。所以不管你用什么算法,你都会有一些精度问题。