nin*_*ini 7 algorithm graph computation-theory hamiltonian-cycle np
我在期中考试时遇到了一个问题.任何人都可以澄清答案吗？
问题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,这是不可能做到的.
我相信答案应该是 1——你不能那样做。原因是您只能对可数集进行二分搜索。
请注意，图的边甚至可能具有负权重，此外，它们还可能具有分数甚至无理数权重。在这种情况下，答案的搜索空间将是所有小于 m 的实数值的集合。
然而，你可能在Log(n)时间内任意接近A的答案，但却无法找到精确的答案。（n 是可数空间的大小）。