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

作者: , 共 1230 字 , 共阅读 0
系列:理论计算机初步

查看该系列所有文章

前面已经提到了显示中大多数难解问题问题最后都被证明是 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 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP-完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在 hash 函数破解上做出重大贡献的王小云教授的工作,不过前两天新闻报道《王小云获得求是杰出科学家奖以及 100 万奖金》,在媒体上又掀起了一轮宣传狂潮,但是有些报道极端弱智,错误百出,所以我趁机纠正一下,并介绍密码学的一个组成部分——hash 函数,以及王小云老师在这上面的工作。
类似文章:
上篇文章已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP-完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
我所学的专业英文名是 Theoretical Computer Science ,理论计算机科学,在这里我就简化成理论计算机了。具体研究些什么呢,下面是Andrew Yao的研究方向
英文是 communication complexity ,不知道该翻译成通信复杂性,还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域,在过去 30 年衍生了很多东西。它是我的研究的主要内容,这里简略介绍一下。
PS: PCP 可以说是理论计算机领域近 20 年来的最重要的结果之一,它给了NP 问题一个新的刻画,并且提供了一种证明近似算法下界的方法。下面是 yijia 写的 PCP 介绍。
注: 这个问题来自China Theory Week 2008的 Open Problems Session。
递归算法的复杂度通常很难衡量,一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大,如果我们可以保存每次子递归的结果的话,递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本On the graph isomorphism problem
密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在 hash 函数破解上做出重大贡献的王小云教授的工作,不过前两天新闻报道《王小云获得求是杰出科学家奖以及 100 万奖金》,在媒体上又掀起了一轮宣传狂潮,但是有些报道极端弱智,错误百出,所以我趁机纠正一下,并介绍密码学的一个组成部分——hash 函数,以及王小云老师在这上面的工作。
转自水木社区Reader版。前不久版上对《平凡的世界》进行了大讨论,这是其中一篇讨论文章。
密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在 hash 函数破解上做出重大贡献的王小云教授的工作,不过前两天新闻报道《王小云获得求是杰出科学家奖以及 100 万奖金》,在媒体上又掀起了一轮宣传狂潮,但是有些报道极端弱智,错误百出,所以我趁机纠正一下,并介绍密码学的一个组成部分——hash 函数,以及王小云老师在这上面的工作。