随机算法初探

随机算法,顾名思义,就是在算法的运行过程中引入了随机机制,因此每次运行得到的结果和运行时间不一样。常见的随机算法有两种Monte Carlo算法 和 Las Vegas算法。

Monte Carlo 算法。算法总能够给出一个结果,不过这个结果是一个随机变量,有一定概率是正确的。其中,给出正确结果的概率是一个大于1/2的数。

Las Vegas算法。算法不一定能在有限时间内给出结果,不过一旦它给出了结果,就一定是正确的。其中,给出结果的概率是一个任意大于0的数。

容易证明,上述两类算法虽然只是以一定概率的到正确结果,但是可以通过运行多次,使得成功概率无限逼近1。

案例1 Ramsey Numbers

“任意6个人的聚会,总能够找出3个互相认识的或者互相不认识的”。相信大家对这个表述并不陌生。归结到数学表示上,它实际上说的是,对于一个有6个顶点的无向图,我们总能找到size为3的独立集(任意两点不相连)或者最大团(任意两点之间均相连)。特别的,我们还有一个数Ramsey Number来表述这一数学问题:


monotone set就是独立集与最大团的合称。更一般的我们有 R(k,l),表示对于保证含有size k的最大团与size l的独立集的图的最小顶点数。

根据对称性,容易得到。一般的,我们可以给出R(k,l)的一个上界的估计: (还没有搞懂)。我们也希望得到它的一个下界。思路也很简单,考虑一个含有n个顶点的随机图。每两个点之间都有的几率有边相连。我们考察这个时候图中找不到size为kmonotone set的概率P(n)。如果概率大于0,那么就说明实际的要比n要大。记V 的导出子图X中找不到monotone set为事件。

随机算法初探_第1张图片
案例2 Satisfiability of Boolean Formulas (SAT)

布尔可满足性问题,指给定一个合取范式(conjunctive norm form),如果能够找到一组变量赋值,使得最后表达式的结果为真,我们则说这个式子是可满足的。

一般来说,这是一个NP问题。但是当给定的式子满足一定条件时,我们能够很轻易得判断他们是否是可满足的。

随机算法初探_第2张图片

证明思路其实很简单。我们一共有种赋值方法。对于子表达式,有种赋值方法使得子表达式不满足。因此,所有的不满足的赋值最多有

所以我们至少能够找到一组赋值,使得给定的合取范式为真。

下面我们可以给出找到这个赋值的方法。思路也很简单,对变量一个一个赋值。比如说,首先对赋值。按照子式中包含的还是,或者不包含,我们将整个合取范式分成三部分A,B,C。当给赋值为0的时候,表达式剩下A'和C;给赋值为1的时候,表达式剩下B'和C。其中A'的子式长度指数和为. B'为.因此,表达式1的指数和为;表达式2的指数和为。将两个式子相加,得到

image.png

两个数相加小于2,其中必有一个数小于1。我们只要选择那个小于1的取值就行。

案例3 Long Path in Graph

在给定的无向图中找到最长路径是一个NP-hard问题。因为在无向图中找到一个Hamiton回路就已经是一个NP-complete问题。我们把要求降低一些,在hamiton图中找到一个长度的路径。下面我们证明,将有一个关于n的多项式时间的算法能够解决这个问题。不过,我们稍微修改一下问题:给定图一种涂色coloring。如果给定路径中每个点的颜色都不相同,我们就说这是一条彩虹路径。问题转变为:给定一个染色图,找到最长的彩虹路径。

首先,我们给出一个算法,它能够在多项式时间内解决上述问题,用到的思想是动态规划。定义:

需要注意的是,是一个集合的集合。其中的元素是集合,是以结尾长度为i的彩虹路径的点的颜色集合。我们希望从中推出。思路也很清楚,我们找到的邻域点集。对于, 考察中每一个元素,也即颜色序列,如果序列中不含有,那么我们可以将和color of v同时加入。以此类推。

算法如下:


随机算法初探_第3张图片

对于给定的长度,最内层循环最大值是.外层两个循环的值为,是图G的边的个数。得到复杂度是,当我们有的时候,复杂度显然是关于n的多项式。(此处有疑问)

接下来回到原来的问题:给定无向图,如何找到长度为的路径。首先,我们分情况讨论:如果不存在,那么显然找不到。如果存在,那么我们可以随机给图上色,然后用上述算法进行求解。如果找到,则问题解决;如果没有找到,并不代表不存在,有可能只是这个涂色方案不合适。我们固定一条路径P,有如下的递推关系:

随机算法初探_第4张图片

注意其中的逻辑转换。有两个重要的不等式
以及

你可能感兴趣的