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

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。