概念
随机算法是能够获得随机性来源（比如随机数生成器）的算法，它允许在很小的概率内出错。计算机科学中最重要的open problems之一就是询问每个高效的随机算法是否都有其对应求解相同问题的确定性算法。
随机算法中的两大经典算法是拉斯维加斯算法和蒙特卡洛算法，其体现了随机算法在时间复杂度和准确度之间的权衡。
这里给出蒙特卡洛算法和拉斯维加斯算法的形式化定义：
蒙特卡洛算法
设$f: \sum ^* \rightarrow \sum ^*$为一个可计算问题，$ 0 \leq \epsilon <1 $为参数，$T:\mathbb N \rightarrow \mathbb N$为一个函数。若$A$为一个随机算法，使得：
$$ \forall x \in {\sum} ^* ,Pr(A(x) \neq f(x)) \leq \epsilon;\\ \forall x \in {\sum} ^* ,Pr(\text{number of steps A(x) takes is at most T(|x|)})=1 $$
则我们声称$A$是一个能够以$T ( {n} ) $时间，$\epsilon$的错误率计算问题$f$的蒙特卡洛算法。蒙特卡洛方法是一种数值计算方法，其原理是通过大量随机样本，去了解一个系统，进而得到所要计算的值。其本质是通过统计学的方法用大量采样取逼近总体。
拉斯维加斯算法
设$f: \sum ^* \rightarrow \sum ^*$为一个可计算问题，$T:\mathbb N \rightarrow \mathbb N$为一个函数。若$A$为一个随机算法，使得：
$$ \forall x \in {\sum} ^* ,Pr(A(x) = f(x)) =1;\\ \forall x \in {\sum} ^* ,E(\text{number of steps A(x) takes }) \leq T(|x|) $$
则我们声称$A$是一个能够以$T(n)$时间计算问题$f$的拉斯维加斯算法。
从定义中我们能够看出，实际上蒙特卡洛算法是在有限时间返回一个大概率正确的解，而拉斯维加斯算法则总是返回一个正确的解，而不侧重于时间的花费。
从采样的角度来说，采样越多，蒙特卡洛算法越近似最优解，而拉斯维加斯算法越有可能找到最优解。
评论(0)