j3jun1 2015-01-02 12:04 采纳率: 100%
浏览 6668
已采纳

为什么说旅行商问题是NP Hard的?

为什么说旅行商问题是NP Hard的?网上看了很多文章还是比较迷糊,有谁能清晰地讲解下。怎么样判断一个算法是不是NP Hard?

  • 写回答

8条回答 默认 最新

  • threenewbee 2015-01-02 12:32
    关注

    怎样证明一个问题C是NP完全问题呢?首先,要证明C是NP问题,也就是C的解的正确性容易验证;然后要证明有一个NP完全问题B,能够在多项式时间内归约到C。这就要求必须先存在至少一个NPC问题。Cook证明了NP完全问题的祖先就是SAT。SAT问题是指给定一个包含n个布尔变量的逻辑式,问是否存在一个取值组合,使得该式被满足。Cook证明了SAT是一个NPC问题,如果SAT容易解决,那么所有NP都容易解决。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(7条)

报告相同问题?