np 40是什么

np 40是什么
09-04-22  匿名提问 发布
2个回答
时间
投票
  • 0

    古西厢

    NP完全性问题 <br><br><br>虽然是计算机系的学生,但自己对于什么是NP问题,<WBR>什么是NPC问题也并不能很好的解答,<WBR>就更不用说构造怎样的一种方式来证明一个 <br>问题是不是NP问题了。但算法中涉及了很多这样的问题,<WBR>压力之下,尽我所能弄懂了,把自己的理解记录下来。 <br><br>P(Polynomial问题)。在计算机里面,<WBR>对一个问题寻求一种多项式的算法是一个很好的解答。<WBR>从理论上来说,如果一个问题能够有多翔 <br>实的解法的话,就算是一个很好的算法了。<WBR>这种问题总可以找到一个DTM(Deterministic Turing Machine) <br><br>NP(Nondeterministic Polynomial问题)。但是对于很多问题来说,<WBR>他们找不到一个多项式的解决方法,他们只能对应一个NDTM(<WBR>Nondeterministic Turing Machine)来解决。可以这样想想:对于下一步的动作,<WBR>他们也不知道确切的应该怎么办,只能“尝试”很多种方案 才能够得出一个答案,这显然是很费时的,这种问题就是NP问题。 <br><br>NPC(NP Complete)问题,可以这么认为,<WBR>这种问题只有把解域里面的所有可能都穷举了之后才能得出答案,<WBR>这样的问题是NP里面最难 <br>的问题,这种问题就是NPC问题。 <br><br>一般说来,如果要证明一个问题是NPC问题的话,<WBR>可以拿已经是NPC问题的一个问题经过多项式时间的变化变成所需<WBR>要证明的问题,那 <br>么索要证明的问题就是一个NPC问题了。 <br><br>NPC问题是一个问题族,如果里面任意一个问题有了多项式的解,<WBR>那么所有的问题都可以有多项式

    09-04-22 | 添加评论 | 打赏

    评论读取中....

精华知识
更多  
意见反馈 帮助