理论计算机初步:概率算法和近似算法

作者:, 发表于

理论计算机初步

查看该系列所有文章

前面已经提到了显示中大多数难解问题问题最后都被证明是NP-完全问题。这意味着,除非NP=P,它们是不可能有多项式时间算法的(而且,在这篇文章提到即使NP=P,人们也可能找不到一个NP完全问题的「有效」算法)。

所以人们发展了各种工具来避开它们,最常用的两种方法是使用概率算法和近似算法,这两种方法也符合实际需要:在解决实际问题中,我们不需要结果绝对正确,也不需要结果绝对精确

所谓概率算法,就是在算法的过程中引入随机数,使得算法在执行的过程中随机选择下一个计算步骤。它最后可能导致结果也是不确定的。一个结果不确定的概率算法叫做Monte Carlo算法,而总是得到准确解的概率算法叫做Sherwood算法(一个例子是引进随机因子的快速排序算法)。

为何引入随机数能够提升计算性能(事实上,理论计算机学家还没能证实随机因子本质上更有效率——指具有指数级别的效率提升),主要有下面两个原因:

首先,通常一个算法,它对于很多种情况是比较快的,但对于某些「特别差」的输入,它要找到一个解则特别困难。引入随机数之后,使得算法的时间复杂度平均化了,然后算得更快(评价一个随机算法的复杂性通常是考虑其平均复杂性)。

其次,对于Monte Carlo算法,它的输出是不精确的,这种牺牲使得算法能够在较短时间内完成。

需要指出的是,下面这个定理,使得一个不那么精确的Monte Carlo算法亦有实际的效用的:

如果一个判定问题的某个Monte Carlo算法有2/3的正确几率(这个2/3可以替换成任何一个大于1/2的数,当然小于等于1/2的随机算法一点意义都没有,因为还不如抛硬币),重复这个算法k次,取出现次数更多的结果作为问题的答案,则这个答案的正确率大于1-1/2(8/9)^k。

上面的结果由于k出现在指数上,所以只需要将一个Monte Carle算法重复很少的次数,便能得到很高的准确率。

近似算法从字面的意思来看似乎和上面的Monte Carle算法差不多,其实它们的考虑对象是不一样的,而且通常所指的近似算法是确定型算法。近似算法多用在组合优化的问题,而不是判定性问题上。组合优化问题,指的是那些需要求最优解的问题,比如下面这个

旅行商问题

有n个城市,一个推销员要从其中某一个城市出发,不重复地走遍所有的城市,再回到他出发的城市。问这个推销员的最短路程。

对于这种问题,如果最短路径是1000,而且我们能很快找到一个1000.1的路径,在实际运用中,我们还需要浪费巨大的计算资源去找那个1000的路径吗?近似算法便基于此思想而来。

近似算法指在解决优化问题中,最后得到的结果能保证在一定的误差之内的算法。

从近似算法的角度来说,同为NP完全问题,它们也有不同的可近似度。在多项式时间内,有些问题可以无穷小误差的逼近,但有些问题却连常数倍数之内的结果都没法得到。

Q.E.D.


上一篇:理论计算机初步:P vs NP - 历史,现状和未来2006年8月24日
上篇文章已经提到,P vs NP是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。

下一篇:理论计算机初步:从hash函数到王小云的MD5破解2006年9月18日
密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在hash函数破解上做出重大贡献的王小云教授的工作,不过前两天王小云获得求是


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。