[科普中国]-随机算法

基本概念

一个随机算法是一种算法，它采用了一定程度的随机性作为其逻辑的一部分。该算法通常使用均匀随机位作为辅助输入来指导自己的行为，超过随机位的所有可能的选择实现了“平均情况下的”良好业绩的希望。从形式上看，该算法的性能将会是一个随机变量，由随机位决定;因此无论是运行时间，或输出（或两者）是随机变量。

在常见的实践中，随机化算法是使用近似的伪随机数发生器代替随机比特的真实来源的;这样的实施可以从预期的理论行为偏离。

解问题P的随机算法定义为：设I是问题P的一个实例，用算法解I的某些时刻，随机选取 ，由

b来决定算法的下一步动作。

优点：1、执行时间和空间，小于同一问题的已知最好的确定性算法；

2、实现比较简单，容易理解；

3、快速且易于并行化。

三要素：输入实例、随机源和停止准则。

一种平衡：随即算法可以理解为在时间、空间和随机三大计算资源中的平衡。2

背景及历史重要方法Monte Carlo求定积分法

随机K-选择法

随机快排序

素性判定的随机算法

二阶段随机路由算法

重要人物和工作de Leeuw等人提出了概率图灵机（1955）

John Gill的随机算法复杂性理论（1977）

Rabin的数论和计算几何领域的工作（1976）

Karp的算法概率分析方法（1985）

Shor的素因子分解量子算法（1994）3

类型分类1、数值概率算法：用于数值问题的求解。所得到的解几乎都是近似解，近似解的精度

随着计算时间的增加而不断地提高。

2、拉斯维加斯算法（LasVegas）：要么给出问题的正确答案，要么得不到答案。反复求解多次，可

使失效的概率任意小。

3、蒙特卡罗算法（MonteCarlo）：总能得到问题的答案，偶然产生不正确的答案。重复运行，每一次

都进行随机选择，可使不正确答案的概率变得任意小。

4、舍伍德算法（Sherwood）：很多具有很好的平均运行时间的确定性算法，在最坏的情况下性能很

坏。引入随机性加以改造，可以消除或减少一般情况和最坏情况的差别。14

时间复杂性衡量确定性算法的时间复杂性，是取它的平均运行时间。

衡量随机算法的时间复杂性，是对确定实例I的期望运行时间，即反复地运行实例I，所取的平均运行时间。

在随机算法里，所讨论的是最坏情况下的期望时间，和平均情况下的期望时间。4

随即算法的设计方法1、挫败对手（Foiling the Adversary）

将不同的算法组成算法群，根据输入实例的不同随机地或有选择地选取不同的算法，以使性能达到最佳。

2、随机采样（Random Sampling）

用“小”样本群的信息，指导整体的求解。

3、随机搜索（Random Search）

是一种简单易行的方法，可以从统计角度分析算法的平均性能，如果将搜索限制在有解或有较多解的区域，可以大大提到搜索的成功概率。

4、指纹技术（Fingerprinting）

利用指纹信息可以大大减少对象识别的工作量。通过随机映射的取值方法，Karp和Rabin得到了一个快速的串匹配随即算法。

5、输入随机重组（Input Randomization）

对输入实例进行随机重组后，可以改进算法的平均性能。

6、负载平衡（Load Balancing）

在并行与分布计算、网络通讯等问题中，使用随机选择技术可以达到任务的负载平衡和网络通讯的平衡。

7、快速混合Markov链（Rapidly Mixing Markov Chain）

使用该方法可以解决大空间中的均匀抽样问题。

8、孤立和破对称技术（Isolation and Symmetry Breaking）

使用该技术可以解决处理的并行性，避免分布式系统的死锁等问题。如：

图着色算法，部分独立集问题。

9、概率存在性证明（Probabilistic Methods and Existence Proofs）

如果随机选取的物体具有某种特性的概率大于0，则具有该特性的物体一定存在。

10、消除随机性（Derandomization）

许多优秀的确定性算法是由随机算法转换而来的。3

随机算法举例Quick Sort（1）传统的快排序算法

总是取第一个元素作为划分元；

算法的最坏运行时间是O( )，平均时间是O( );

因此存在一些输入实例，使得算法达到最坏运行时间

如：降序的序列；

（2）随即快排序算法

随机选择一个元素作为划分元；

任何一个输入的期望时间是O（ ）；

这是一个Las Vegas算法；

Min Cut（1）最小截问题定义：

给定一个无向图G(V,E),找一个截（V1,V2）使得V1和V2间的连边数最小。

（2）该问题可以用确定性算法（max-flow min-cut algorithm）在O( )时间内完成。

（3）随机算法

随机选一条边，将两顶点合一并除去顶点上的环；

直到图中只剩下两个顶点；

返回剩下两顶点建德连边数；

（4）示例：#cut=2

（5）出错概率

重复K次出错概率为

(6)本算法是一个Monte Carlo型算法3