3 随机算法简介.pdf

Randomized Algorithms 随机算法 陈卫东 chenwd@scnu.edu.cn 华南师范大学 计算机学院 2009-10-9 随机算法（概率算法） 引言 数值随机算法 舍伍德算法（Sherwood ） 拉斯维加斯算法（Las Vegas ） 蒙特卡洛算法（Monte Carlo ） W.D.Chen South China Normal University 1 引言 随机算法的特点 随机算法允许算法在执行过程中随机地选择某些计算步骤。 相同实例上运行同一随机算法多次可能会产生不同效果。 （所得结果不同或求解效率不同，甚至差别很大） 可能对某些输入产生不正确的结果。 易于理解、设计和实现 时空性能往往比确定性算法要好 随机算法的期望时间 实例上的期望时间——算法多次在该实例上运行的平均时间 算法最坏（平均、最好）期望时间 W.D.Chen South China Normal University 2 引言 随机算法的适用问题 问题求解中面临一个抉择时，随机性选择常常或比确定性选择省时 或者效果更好。这些问题使用随机算法可在很大程度上降低算法复 杂度。 某些问题使用确定型算法求解非常耗时，此时考虑使用随机算法往 往可快速得到一个较为满意的解。 随机算法的类型 数值随机算法 舍伍德算法（Sherwood） 拉斯维加斯算法（Las Vegas ） 蒙特卡洛算法（Monte Carlo ） W.D.Chen South China Normal University 3 数值随机算法 算法特点 数值随机算法常用于求解数值问题的解。这类算法所得的解往往是 近似解，且近似解的精度随着计算时间的增加而不断提高。在许多情 况下，要计算问题的精确解是不可能的或没有必要，而用数值随机算 法可得到相当满意的解。 例如，可用数值随机算法求： π的近似值 定积分的近似值 方程的近似解… W.D.Chen South China Normal University 4 数值随机算法 用随机投点法来计算π的值 算法思路 设有一个半径为r 的圆及其 外切正方形。向该正方形中随 机投n个点。设落入圆内的点数 为k 。则 π≈4k/n 算法（略） W.D.Chen South China Normal University 5 数值随机算法 用随机投点法来计算定积分 已知0≤f (x)≤1，0≤x≤1，需要计算 I=∫ 1 0 f (x)dx 算法思路 f (x) 设有一个边长为1的正方形。向该正 方形中随机投n个点。设落入下面区域 中的点数记作m 。则 I≈m/n 算法（略） W.D.Chen South China Normal University 6 舍伍德算法（Sherwood） 算法特点 当一个确定型算法