(算法分析的设计）第7章随机化算法.pptVIP

第7章 随机化算法 概率算法 概率算法 同前几章算法的区别 概率算法允许算法在执行过程中随机地选择下一个计算步骤。 在许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。 概率算法的一个基本特征：对所求解问题的同一实例用同一概率算法求解两次，可能得到完全不同的效果。 反映在求解时间、结果质量等方面。 分析困难：要求有概率论，统计学和数论的知识 概率算法的主要类型 概率算法的主要类型 数值概率算法 舍伍德算法 拉斯维加斯算法 蒙特卡罗算法 随机性被最早用于求数字问题的近似解 例如，求一个系统中队列的平均长度的问题，确定算法很难得到答案 概率算法获得的答案一般是近似的，但通常算法执行的时间越长，精度就越高，误差就越小 使用的理由 现实世界中的问题在原理上可能就不存在精确解 例如，实验数据本身就是近似的，一个无理数在计算机中只能近似地表示 精确解存在但无法在可行的时间内求得 有时答案是以置信区间的形式给出的 数值概率算法 舍伍德算法 舍伍德算法 总能求解得到问题的一个解，而且所求得的解总是正确的。 当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可在这个确定算法中引入随机性，将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的差别。 如快速排序法：O(n2)(出现概率小); O(nlogn); 舍伍德算法的精髓 不是避免算法的最坏情况，而是设法消除这种最坏情形行为与特定实例之间的关联性。 数据洗牌+确定算法； 提纲 随机数 数值概率算法 舍伍德算法 拉斯维加斯算法 蒙特卡罗算法 本章小结 随机数 随机数 在科学计算中扮演非常重要的角色。 现有的随机数产生器所产生的随机数都是伪随机数 在一定程度上是随机的 常用的随机数产生方法 线性同余法 线性同余法 该随机序列的种子 如何选取常数b、c、m将直接影响到所产生随机序列的随机性。 设b=3,c=7,m=127,d=2,则有 (13,46,18,61,63,69,87,14,49,27,88,17,……) 提纲 随机数 数值概率算法 舍伍德算法 拉斯维加斯算法 蒙特卡罗算法 本章小结 数值概率算法 用随机投点法计算π值 计算定积分 用随机投点法计算π值 算法思想 设有一半径为r的圆及其外切四边形。向该正方形随机投掷n个点。落入圆内的点数为k。 double Darts(int n) { // 用随机投点法计算π值 static RandomNumber dart; int k=0; for (int i=1;i =n;i++) { double x= uniform(0, 1); double y= uniform(0, 1); if ((x*x+y*y)=1) k++; } return 4*k/double(n); } 实验结果： π=3.141592654 n = 1000万: 3.140740, 3.142568 (2位精确) n = 1亿: 3.141691, 3.141363 (3位精确) n = 10亿: 3.141527, 3.141507 (4位精确) 计算定积分 用随机投点法计算定积分 用平均值法计算定积分 用随机投点法计算定积分 Y=f(x) G x y 1 0 1 提纲 随机数 数值概率算法 舍伍德算法 拉斯维加斯算法 蒙特卡罗算法 本章小结 舍伍德算法 舍伍德算法 目的：设法消除最坏情形行为与特定实例之间的关联性。 其计算时间复杂性对所有实例而言相对均匀，但同相应的确定性算法相比，其平均时间复杂性没有改进。 可以用下面的洗牌算法Shuffle将数组a中元素随机排列，然后用确定性选择算法求解。 templateclass Type void Shuffle(Type a[], int n) { // 随机洗牌算法 static RandomNumber rnd; for (int i=0;in;i++) { int j=rnd.Random(n-i)+i; Swap(a[i], a[j]); } } 提纲 随机数 数值概率算法 舍伍德算法 拉斯维加斯算法 蒙特卡罗算法 本章小结 拉斯维加斯算法 拉斯维加斯算法(Las Vegas) 能够显著改进算法的有效性，对某些目前还找不到有效算法的问题，也能得到较为满意的算法 不会得到不正确的解，但有时找不到问题的解　 通常用boolean型方法来表示拉斯维加斯算法 找到解，返回true; 未找到解，返回false; 此时，可以对同一实例再次调用相同的算法 由随机算法的性质决定 效率分析 Public static void obstinate( Object x, Object y) { 　boo