小角色,大心脏

C++博客 首页 新随笔 联系 聚合 管理
  6 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks
某此报告会上,提到NP问题,不是清楚,现查阅如下:
1)http://en.wikipedia.org/wiki/NP-hard上的解释;
2)弄清楚这几个概念:计算复杂性以及其排序和问题规约等;
##计算复杂性
这是描述一种算法需要多少“时间”的度量。(也有空间复杂性,但因为它们能相互转换,所以通常我们就说时间复杂性。对于大小为 n 的输入,我们用含 n 的简化式子来表达。(所谓简化式子,就是忽略系数、常数,仅保留最“大”的那部分)
比如找出 n 个数中最大的一个,很简单,就是把第一个数和第二个比,其中大的那个再和第三个比,依次类推,总共要比 n-1 次,我们记作 O(n) (对于 n 可以是很大很大的情况下,-1可以忽略不计了)。
再比如从小到大排好的 n 个数,从中找出等于 x 的那个。一种方法是按着顺序从头到尾一个个找,最好情况是第一个就是 x,最坏情况是比较了 n 次直最后一个,因此最坏情况下的计算复杂度也是 O(n)。还有一种方法:先取中间那个数和 x 比较,如偏大则在前一半数中找,如偏小则在后一半数中找,每次都是取中间的那个数进行比较,则最坏情况是 lg(n)/lg2。忽略系数lg2,算法复杂度是O(lgn)。

##计算复杂性的排序:
根据含 n 的表达式随 n 增大的增长速度,可以将它们排序:1 < lg(n) < n < nlg(n) < n^2 < ... < n^k (k是常数)< ... < 2^n。最后这个 2 的 n 次方就是级数增长了,读过棋盘上放麦粒故事的人都知道这个增长速度有多快。而之前的那些都是 n 的多项式时间的复杂度。为什么我们在这里忽略所有的系数、常数,例如 2*n^3+9*n^2 可以被简化为 n^3?用集合什么的都能解释,我忘了精确的说法了。如果你还记得微积分的话就想像一下对 (2*n^3+9*n^2)/(n^3) 求导,结果是0,没区别,对不?

##P 问题:对一个问题,凡是能找到计算复杂度可以表示为多项式的确定算法,这个问题就属于 P (polynomial) 问题。

##NP 问题:
NP 中的 N 是指非确定的(non-deterministic)算法,这是这样一种算法:(1)猜一个答案。(2)验证这个答案是否正确。(3)只要存在某次验证,答案是正确的,则该算法得解。
NP (non-deterministic polynomial)问题就是指,用这样的非确定的算法,验证步骤(2)有多项式时间的计算复杂度的算法。

##问题的归约:
这……我该用什么术语来解释呢?集合?太难说清了……如果你还记得函数的映射的话就比较容易想象了。
大致就是这样:找从问题1的所有输入到问题2的所有输入的对应,如果相应的,也能有问题2的所有输出到问题1的所有输出的对应,则若我们找到了问题2的解法,就能通过输入、输出的对应关系,得到问题1的解法。由此我们说问题1可归约到问题2。

##NP-Hard:
有这样一种问题,所有 NP 问题都可以归约到这种问题,我们称之为 NP-hard 问题。

##NP完全问题 (NP-Complete):
如果一个问题既是 NP 问题又是 NP-Hard 问题,则它是 NP-Complete 问题。可满足性问题就是一个 NP 完全问题,此外著名的给图染色、哈密尔顿环、背包、货郎问题都是 NP 完全问题。

从直觉上说,P<=NP<=NP-Complete<=NP-Hard,问题的难度递增。但目前只能证明 P 属于 NP,究竟 P=NP 还是 P 真包含于 NP 还未知。
posted on 2011-06-21 10:05 小角色 阅读(121) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理