随机算法初探

作者: Corn_48ad | 来源:发表于2018-09-21 15:58 被阅读0次

随机算法，顾名思义，就是在算法的运行过程中引入了随机机制，因此每次运行得到的结果和运行时间不一样。常见的随机算法有两种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的最大团与sizel的独立集的图的最小顶点数。

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

案例2 Satisfiability of Boolean Formulas (SAT)

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

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

证明思路其实很简单。我们一共有 $2^n$ 种赋值方法。对于子表达式 $C_i$ ，有 $2^{n-l_i}$ 种赋值方法使得子表达式不满足。因此，所有的不满足的赋值最多有

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

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

image.png

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

案例3 Long Path in Graph

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

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

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

算法如下：

对于给定的长度 $i$ ，最内层循环最大值是 ${k}\choose{i}$ .外层两个循环的值为 $2*m$ ， $m$ 是图G的边的个数。得到复杂度是 $O(2^k)2m$ ,当我们有 $k=\log n$ 的时候，复杂度显然是关于n的多项式。（此处有疑问）

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

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

1-x <= e^{-x}

以及

k! >( \frac{k}{e})^k

随机算法初探

案例1 Ramsey Numbers

案例2 Satisfiability of Boolean Formulas (SAT)

案例3 Long Path in Graph

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读