为什么说旅行商问题是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都容易解决。
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报