随机化算法.pdf

补充4 随机化算法
z 理解产生伪随机数的算法
z 掌握数值随机化算法的设计思想
z 掌握蒙特卡罗算法的设计思想
z 掌握拉斯维加斯算法的设计思想
z 掌握舍伍德算法的设计思想
1
算法导论
Sch4-1 方法概述
2
算法导论
Sch4-1 方法概述
z 定义：是一个概率图灵机。也就是在算法中引入随机因素，即通过随
机数选择算法的下一步操作。
z 三要素：输入实例、随机源和停止准则。
z 特点：简单、快速和易于并行化。
z 一种平衡：随机算法可以理解为在时间、空间和随机三大计算资源中
的平衡（Lu . 博士论文,1999）
z 重要文献：Motwani R. and Raghavan P., Randomized Algorithms.
Cambridggye University Press, New York, 1995
3
算法导论
Sch4-1 方法概述
z 著名的例子
— Monte Carlo求定积分法
— 随机k-选择算法
— 随机快速排序
— 素性判定的随机算法
— 二阶段随机路由算法
z 重要人物和工作
— De Leeuw等人提出了概率图灵机（1955）
— John Gill的随机算法复杂性理论（1977）
— Rabin的数论和计算几何领域的工作（1976）
— Karp的算法概率分析方法（1985）
— Shor的素因子分解量子算法（1994）
4
算法导论
Sch4-1 方法概述
z 常见的随机算法分为4类：
① 数值随机化算法：常用于数值问题的求解，所得到的往往是近似解，
解的精度随着计算时间增加而不断提高；
② 蒙特卡罗算法：用于求问题的准确解。该方法可以得到的解，但是该
解未必是正确的。求得正确解的概率依赖于算法所用的时间。比较难
以判断解是否正确；
③ 拉斯维加斯算法：不会得到不正确的解，但是有时会找不到解。找到
正确解的概率随着所用的计算时间的增加而提高。对任一实例，反复
调用算法求解足够多次，可使求解失效的概率任意小；
④ 舍伍德算法：总能求得问题的一个解，且所求得的解总是正确的。当
一个确定性算法最坏情况下的计算复杂性与其在平均情况下的计算复
杂性有较大差别时，可在这个确定性算法中引入随机性将它改造成一
个舍伍德算法，消除或者减少这种差别。核心思想是：设法消除最坏
情形行为与特定实例之间的关联性。
5
算法导论
Sch4-2 随机数
z 随机数在随机化算法设计中扮演着十分重要的角色。在现实计算机上
无法产生真正的随机数，因此在随机化算法中使用的随机数都是一定
程度上随机的，即伪随机数。
z 线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随
机序列a0,a1,…,an满足
⎧a0 = d
⎨
⎩an = (ban−1 + c) mod m n = 1,2,Λ
其中b≥0，c≥0，d≤m。d称为该随机序列的种子。如何选取该方法中
的常数b、c和m直接关系到所产生的随机序列的随机性能。这是随机
性理论研究的内容，已超出本书讨论的范围。从直观上看，m应取得
充分大，因此可取m为机器大数，另外应取gcd(m,b)1)=1，因此可取b
为一素数。
6
算法导论
Sch4-2 随机数
z 随机整数算法：
利用线性同余式计算新的种子，将randSeed右移16位得到一个0‾65535
间的随机数，然后再将此随机整数映射到0‾(n-1)范围内。
Random（n, s）
{ //产生 0:n0 : n-