清华大学出版社：《算法设计与分析》课程教学资源（PPT课件讲稿）第7章 概率算法

清华大学出版社 TSINGHUA UNIVERSITY PRESS 第7章概率算法

1 第7章 概率算法

清华大学出版社 随机数 VERSITY PRESS 随机数在概率算法设计中扮演着十分重要的角色。在现实计算机 上无法产生真正的随机数,因此在概率算法中使用的陌随机数都是 定程度上随机的,即伪随机数 线性同余法是产生伪随机数的最常用的方法。由线性同余法产生 的随机序列a,a1,an满足 an=(ba,- +c)mod m n=1, 2 其中b0,c≥0,d≤m。d称为该随机序列的种子。如何选取该 方法中的常数b、c和m直接关系到所产生的随机序列的随机性 能。这是随机性理论研究的内容,已超出本书讨论的范围。从 直观上看,m应取得充分大,因此可取m为机器大数,另外应 取gcd(m,b)=1,因此可取b为一素数。 2

2 随机数 随机数在概率算法设计中扮演着十分重要的角色。在现实计算机 上无法产生真正的随机数，因此在概率算法中使用的随机数都是 一定程度上随机的，即伪随机数。 线性同余法是产生伪随机数的最常用的方法。由线性同余法产生 的随机序列a0 ,a1 ,…,an满足    = + = = ( −1 )mod 1,2, 0 a ba c m n a d n n 其中b0，c0，dm。d称为该随机序列的种子。如何选取该 方法中的常数b、c和m直接关系到所产生的随机序列的随机性 能。这是随机性理论研究的内容，已超出本书讨论的范围。从 直观上看，m应取得充分大，因此可取m为机器大数，另外应 取gcd(m,b)=1，因此可取b为一素数

清华大学出版社 TSINGHUA UNIVERSITY PRESS 数值概率算法

3 数值概率算法

清华大学出版社 用随机投点法讦算元值 设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个 点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分 布,因而所投入的点落入圆内的概率为=x。所以当n足够大 4k 时,k与n之比就逼近这一概率。从而丌 public static double darts(int n) ∥用随机投点法计算π值 int k=0 for(int i=1; i <=n; i++)i double dart. fRandomo double y=dart. fRandomO if((X*X+y*y)<=1k++; return 4 k/double)n 4

4 用随机投点法计算值 设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个 点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分 布，因而所投入的点落入圆内的概率为 。所以当n足够大 时，k与n之比就逼近这一概率。从而 。 4 4 2 2   = r r n 4k   public static double darts(int n) { // 用随机投点法计算值 int k=0; for (int i=1;i <=n;i++) { double x=dart.fRandom(); double y=dart.fRandom(); if ((x*x+y*y)<=1) k++; } return 4*k/(double)n; }

清华大学出版社 计算定积分 IY PRESS 设印(x)是[0,1上的连续函数,且0≤f(x)≤1。 需要计算的积分为/=「(x)积分等于图中的面积G 0 y=f(x) 在图所示单位正方形内均匀地作投点试验,则随机点落在曲线下 面的概率为 P{y≤f(x)=「∫dak=∫f(xk 假设向单位正方形内随机地投入n个点(x,y)。如果有m个点落入 G内,则随机点落入G内的概率Ⅰ≈

5 计算定积分 设f(x)是[0，1]上的连续函数，且0f(x)1。 需要计算的积分为 =  ,积分I等于图中的面积G。 1 0 I f (x)dx 在图所示单位正方形内均匀地作投点试验，则随机点落在曲线下 面的概率为 假设向单位正方形内随机地投入n个点(xi,yi)。如果有m个点落入 G内，则随机点落入G内的概率     = = 1 0 ( ) 0 1 0 { ( )} ( ) f x Pr y f x dydx f x dx n m I 

清华大学出版社 解非线性方程组 RESS 求解下面的非线性方程组 f(x1,x2,…xn)=0 f2(xu,x )=0 X.x )=0 其中,x1,X2,…,xn是实变量,f是未知量X1,X2…,xn的非线性实函 数。要求确定上述方程组在指定求根范围内的组解x,x2;…x 在指定求根区域D内,选定一个随机点x作为随机搜索的出发 点。在算法的搜索过程中,假设第步随机搜索得到的随机搜 索点为X。在第+1步,计算出下一步的随机搜索增量ΔX。从 当前点依A得到第+1步的随机搜索点。当X时,取为所求 非线性方程组的近似解。否则进行下—步新的随机搜索过程

6 解非线性方程组 求解下面的非线性方程组        = = = ( , , , ) 0 ( , , , ) 0 ( , , , ) 0 1 2 2 1 2 1 1 2 n n n n f x x x f x x x f x x x     其中，x1 ,x2 ,…,xn是实变量，f i是未知量x1 ,x2 ,…,xn的非线性实函 数。要求确定上述方程组在指定求根范围内的一组解 * * 2 * 1 , , , n x x  x 在指定求根区域D内，选定一个随机点x0作为随机搜索的出发 点。在算法的搜索过程中，假设第j步随机搜索得到的随机搜 索点为xj。在第j+1步，计算出下一步的随机搜索增量xj。从 当前点xj依xj得到第j+1步的随机搜索点。当x<时，取为所求 非线性方程组的近似解。否则进行下一步新的随机搜索过程

清华大学出版社 TSINGHUA UNIVERSITY PRESS 舍伍德( Sherwood)算法 设A是一个确定性算法,当它的输入实例为刈时所需的计算时间记 为tA(∞。设Ⅹ是算法A的输入规模为η的实例的全体,则当问题的 输入规模为n时,算法A所需的平均时间为 t(m)=∑t1(x)/|Xn 这显然不能排除存在ⅹ∈Ⅺn使得t1(x)>A(n)的可能性。希望获得 个概率算法B,使得对问题的输入规模为η的每一个实例均有 tB(x=ta(n+s(n) 这就是舍伍德算法设计的基本思想。当s(η)与tm框比可忽略时, 舍伍德算法可获得很好的平均性能

7 舍伍德(Sherwood)算法 设A是一个确定性算法，当它的输入实例为x时所需的计算时间记 为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的 输入规模为n时，算法A所需的平均时间为   = Xn x A n t A (n) t (x) / | X | 这显然不能排除存在x∈Xn使得 的可能性。希望获得 一个概率算法B，使得对问题的输入规模为n的每一个实例均有 这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时， 舍伍德算法可获得很好的平均性能。 t (x) t A (n) A  t (x) t A (n) s(n) B = +

班舍伍德( Sherwood算法 复习学过的 Sherwood算法 1)线性时间选择算法 2)快速排序算法 有时也会遇到这样的情况,即所给的确定性算法无法直接改造成 舍伍德型算法。此时可借助于随机预处理技术,不改变原有的 确定性算法,仅对其输入进行随机洗牌,同样可收到舍伍徳算 法的效果。例如,对于确定性选择算法,可以用下面的洗牌算 法 shuffle将数组a中元素随机排列,然后用确定性选择算法求 解。这样做所收到的效果与舍伍德型算法的效果是一样的。 public static void shuffle(Comparable [a, int n) 随机洗牌算法 rnd= new Random for(int i=1; i<n; i ++)i int j=rnd random(n-i+1)+i; MyMath. swap(a, 1, j

8 舍伍德(Sherwood)算法 复习学过的Sherwood算法： （1）线性时间选择算法 （2）快速排序算法 有时也会遇到这样的情况，即所给的确定性算法无法直接改造成 舍伍德型算法。此时可借助于随机预处理技术，不改变原有的 确定性算法，仅对其输入进行随机洗牌，同样可收到舍伍德算 法的效果。例如，对于确定性选择算法，可以用下面的洗牌算 法shuffle将数组a中元素随机排列，然后用确定性选择算法求 解。这样做所收到的效果与舍伍德型算法的效果是一样的。 public static void shuffle(Comparable []a, int n) {// 随机洗牌算法 rnd = new Random(); for (int i=1;i<n;i++) { int j=rnd.random(n-i+1)+i; MyMath.swap(a, i, j); } }

清华大学出版社 跳跃表 ERSITY PRESS 舍伍德型算法的设计思想还可用于设计高效的数据结构。 如果用有序链表来表示一个含有η个元素的有序集S,则在最坏 情况下,搜索S中一个元素需要Ω(η)计算时间。 提高有序链表效率的一个技巧是在有序链表的部分结点处增设 附加指针以提高其搜索性能。在增设附加指针的有序链表中搜 索一个元素时,可借助于附加指针跳过链表中若干结点,加快 搜索速度。这种增加了向前附加指针的有序链表称为跳跃表。 应在跳跃表的哪些结点增加附加指针以及在该结点处应增加多 少指针完全采用随机化方法来确定。这使得跳跃表可在O(ognη) 平均时间内支持关于有序集的搜索、插入和删除等运算。 →2|*3|心++9+2 (b) 2|3|5|一+923

9 跳跃表 •舍伍德型算法的设计思想还可用于设计高效的数据结构。 •如果用有序链表来表示一个含有n个元素的有序集S，则在最坏 情况下，搜索S中一个元素需要(n)计算时间。 •提高有序链表效率的一个技巧是在有序链表的部分结点处增设 附加指针以提高其搜索性能。在增设附加指针的有序链表中搜 索一个元素时，可借助于附加指针跳过链表中若干结点，加快 搜索速度。这种增加了向前附加指针的有序链表称为跳跃表。 •应在跳跃表的哪些结点增加附加指针以及在该结点处应增加多 少指针完全采用随机化方法来确定。这使得跳跃表可在O(logn) 平均时间内支持关于有序集的搜索、插入和删除等运算

清华大学出版社 跳跃表 YERSITY PRESS 在一般情况下,给定一个含有n个元素的有序链表,可以将它改 造成一个完全跳跃表,使得每一个k级结点含有k+1个指针,分 别跳过2-1,2k1-1,,20-1个中间结点。第k级结点安排在 跳跃表的位置i2k处,≌0。这样就可以在时间o(ogn)内完成集合 成员的搜索运算。在一个完全跳跃表中,最高级的结点是gn 级结点。 °02|+3|+5|+13+17|19|2 旧,,,口啦目,: 完全跳跃表与完全二叉搜索树的情形非常类似。它虽然可以有 效地支持成员搜索运算,但不适应于集合动态变化的情况。集 元素的插入和删除运算会破坏完全跳跃表原有的平衡状态 影响后继元素搜索的效率

10 跳跃表 在一般情况下，给定一个含有n个元素的有序链表，可以将它改 造成一个完全跳跃表，使得每一个k级结点含有k+1个指针，分 别跳过2 k -1，2 k-1 -1，…，2 0 -1个中间结点。第i个k级结点安排在 跳跃表的位置i2k处，i0。这样就可以在时间O(logn)内完成集合 成员的搜索运算。在一个完全跳跃表中，最高级的结点是logn 级结点。 完全跳跃表与完全二叉搜索树的情形非常类似。它虽然可以有 效地支持成员搜索运算，但不适应于集合动态变化的情况。集 合元素的插入和删除运算会破坏完全跳跃表原有的平衡状态， 影响后继元素搜索的效率