简述随机化算法

本篇将主要讲解随机化算法，在正式进入主题之前，我们先谈谈什么是随机化？随机化是一种可能影响试验结果的无关或可能在试验过程中变化，从而影响到最终结果。

随机化算法，是在算法中使用了随机函数，且随机函数的返回值直接或间接的影响了算法的执行流程或结果。随机化算法基于随机方法，依赖于概率大小。

一、随机化算法分类

通俗的说，就是在算法执行的某个步骤中将生成随机数，而该随机数将会影响到整个算法的最终结果。因此，我们可以将随机算法大致分为以下两类：

（1）蒙特卡洛算法(Monte Carlo)并不是一种具体的算法，而是一类算法的统称。其基本思想是基于随机事件出现的概率。蒙特卡洛算法得到的最终结果并不一定是正确的，我们可以通过计算算法出错的概率值，然后进行多次求解，使得最终得到正确结果的可能性变得很高。接下来我们来讨论一种蒙特卡洛算法：

（2）拉斯维加斯算法 (Las Vegas) 是另一种随机算法，因此它具备随机算法最为重要的特征之一 —— 基于随机数进行求解。和蒙特卡洛算法一样，都是一类随机算法,所以就分别用了两个赌城的名字命名,其实和拉斯维加斯没关系，与 蒙特卡洛算法 (Monte Carlo) 一样，拉斯维加斯算法也不是一种具体的算法，而是一种思想。但不同的是，拉斯维加斯算法在生成随机值的环节中，会不断的进行尝试，直到生成的随机值令自己满意。在这过程中也许会一直无法产生这样的随机值，因此拉斯维加斯算法的时间效率通常比蒙特卡洛算法来的低，并且最终可能无法得到问题的解，但是一旦算法找到一个解，那么这个解一定是问题的正确解。

二、随机数与伪随机数

说一个单独的数是「随机数」是无意义的，所以以下我们都默认讨论「随机数列」，即使提到「随机数」，指的也是「随机数列中的一个元素」。

现有的计算机的运算过程都是确定性的，因此，仅凭借算法来生成真正 不可预测、不可重复 的随机数列是不可能的。

然而在绝大部分情况下，我们都不需要如此强的随机性，而只需要所生成的数列在统计学上具有随机数列的种种特征（比如均匀分布、互相独立等等）。这样的数列即称为 伪随机数 序列。

随机数与伪随机数在实际生活和算法中的应用举例：

抽样调查时往往只需使用伪随机数。这是因为我们本就只关心统计特征。

网络安全中往往要用到（比刚刚提到的伪随机数）更强的随机数。这是因为攻击者可能会利用可预测性做文章。

OI/ICPC 中用到的随机算法，基本都只需要伪随机数。这是因为，这些算法往往是 通过引入随机数 来把概率引入复杂度分析，从而降低复杂度。这本质上依然只利用了随机数的统计特征。

某些随机算法（例如 Moser 算法）用到了随机数的熵相关的性质，因此必须使用真正的随机数。

随机化算法在考试中出现的次数不是很多，但是出现了，使用好会节省很多时间和经历，所以大家一定要记住随机化是一种可能影响试验结果的无关或可能在试验过程中变化，从而影响到最终结果，慎重选择。