相关疑难解决方法(0)

我在期中考试时遇到了一个问题.任何人都可以澄清答案吗？

问题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,这是不可能做到的.