算法分析——6.ppt

算法设计与分析 ——概率算法 概率算法 概率算法 同前几章算法的区别 概率算法允许算法在执行过程中随机地选择下一个计算步骤。 在许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。 概率算法的一个基本特征：对所求解问题的同一实例用同一概率算法求解两次，可能得到完全不同的效果。 反映在求解时间、结果质量等方面。 概率算法的主要类型 概率算法的主要类型 数值概率算法 蒙特卡罗算法 拉斯维加斯算法 舍伍德算法 数值概率算法 数值概率算法 常用于数值问题的求解，得到的往往是近似解 解的精度随计算时间的增加而提高 在许多情况下，计算出问题的精确解是不可能或没必要 蒙特卡罗算法 蒙特卡罗算法 用于求解问题的准确解 在有些情况下，近似解没有意义，比如“0/1”判定问题 可以求得问题的一个解，但该解未必正确 求得正确解的概率依赖于算法的计算时间 蒙特卡罗算法的主要缺点就在于无法有效判定所得到的解是否肯定正确。 拉斯维加斯算法 拉斯维加斯算法 不会得到不正确的解 但有时找不到问题的解 找到正确解的概率随算法计算时间的增加而提高 用同一拉斯维加斯算法反复对问题实例求解足够多次，可使求解失败的概率任意小。 舍伍德算法 舍伍德算法 总能求解得到问题的一个解，而且所求得得解总是正确的。 当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可在这个确定算法中引入随机性，将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的差别。 舍伍德算法的精髓 不是避免算法的最坏情况，而是设法消除这种最坏情形行为与特定实例之间的关联性。 提纲 随机数 数值概率算法 舍伍德算法 拉斯维加斯算法 蒙特卡罗算法 本章小结 提纲 随机数 数值概率算法 舍伍德算法 拉斯维加斯算法 蒙特卡罗算法 本章小结 随机数 随机数 在科学计算中扮演非常重要的角色。 现有的随机数产生器所产生的随机数都是伪随机数 在一定程度上是随机的 常用的随机数产生方法 线性同余法 线性同余法 随机序列的产生与实验 随机序列的产生 参看教材242 Random fRandom 模拟抛硬币实验 参看教材244 提纲 随机数 数值概率算法 舍伍德算法 拉斯维加斯算法 蒙特卡罗算法 本章小结 通过实例学习数值概率算法 用随机投点法计算π值 计算定积分 解非线性方程组 用随机投点法计算π值 算法思想 设有一半径为r的圆及其外切四边形。向该正方形随机投掷n个点。落入圆内的点数为k。 计算定积分 用随机投点法计算定积分 用平均值法计算定积分 用随机投点法计算定积分 用平均值法计算定积分 算法实现 用随机投点法计算定积分 参看教材246 用平均值法计算定积分 参看教材247 解非线性方程组 利用概率算法求解 算法改进 概率算法在求解非线性方程组时，虽然有些耗时，但实际应用中还是比较有效的，对于那些精度要求较高的问题，概率算法往往会为其提供一个较好的初始值。 算法实现过程参看教材249 提纲 随机数 数值概率算法 舍伍德算法 拉斯维加斯算法 蒙特卡罗算法 本章小结 舍伍德算法 舍伍德算法 目的：设法消除最坏情形行为与特定实例之间的关联性。 其计算时间复杂性对所有实例而言相对均匀，但同相应的确定性算法相比，其平均时间复杂性没有改进。 实例说明 线性时间选择 跳跃表 线性时间选择 线性时间选择 问题所在：选择合适的划分基准 对于选择问题，用拟中位数作为划分基准可以保证在最坏情况下用线性时间完成选择。 舍伍德型选择算法 随机选择一个组元素作为划分基准，既保证算法的线性时间平均性能，又可以避免计算中位数的麻烦。 Select算法分析 Select算法分析 结论 结论 非递归的舍伍德型选择算法Select可以在O(n)平均时间内找出ｎ个输入元素中的第ｋ小元素 提示 对于某些确定性算法，可以将其改造成舍伍德算法，使得该算法以高概率对任何实例均有效。 对于某些不能直接改造的情况，可以借助预处理技术，不改变原有的确定性算法，而仅对其输入元素进行随机洗牌，同样可以收到舍伍德算法的效果。 跳跃表 跳跃表 如果用有序链表来表示一个含有ｎ个元素的有序集合Ｓ，则在最坏情况下，有哪些信誉好的足球投注网站Ｓ中的一个元素需要Ω(n)计算时间。为了跳高效率，可以在部分结点处增加附加指针来提高有哪些信誉好的足球投注网站性能（借助这些附加指针，可以跳过链表中的若干结点，从而加快有哪些信誉好的足球投注网站速度）。这种增加了向前附加指针的有序链表称为跳跃表。 举例说明 如何进行有哪些信誉好的足球投注网站？ 如何在该跳跃表中有哪些信誉好的足球投注网站元素８？ 有序链表?跳跃表 存在的问题 随机算法的引入 解决方案 采用随机化方法来确定附加指针的增加结点位置和数量。使得跳跃表可以在O(logn)平均时间内支持关于有序集的有哪些信誉好的足球投注网站、插入和删除等运算操作。 实现方案参看教材256 附加指针的平衡性 解决方案 随机生成新