东南大学：《数据结构》课程教学资源（PPT课件讲稿）随机算法（主讲：方效林）

随机算法 东南大学计算机学院方效林

东南大学计算机学院 方效林 随机算法

本章内容 随机算法的基本概念 随机采样问题 第k小元素问题的随机算法 Sherwood随机化方法 判断字符串是否相等问题 子串匹配问题 求最近点对的随机算法 素数测试

本章内容 ◼ 随机算法的基本概念 ◼ 随机采样问题 ◼ 第k小元素问题的随机算法 ◼ Sherwood随机化方法 ◼ 判断字符串是否相等问题 ◼ 子串匹配问题 ◼ 求最近点对的随机算法 ◼ 素数测试 2

随机算法的基本概念 例子 o判断函数f(x1,x2X)在区域D中是否恒为0, 2 f很复杂,不能数学化简,如何判断就很麻烦 o若随机产生一个n维坐标(r2)D,代入 得f(r,2rn)≠0,则可判定区域D内f不恒为0 o若对很多个随机产生的坐标进行测试,结果次 次均为0,则可说f0的概率是非常小 有不少问题,目前只有效率很差的确定性求解 算法,但用随机算法去求解,可以很快地获 得相当可信的结果 3

随机算法的基本概念 ◼ 例子  判断函数 f(x1 ,x2 ,…xn )在区域 D中是否恒为0， f 很复杂，不能数学化简，如何判断就很麻烦  若随机产生一个n维坐标(r1 ,r2 ,… rn )D，代入 得f(r1 ,r2 ,… rn )≠0，则可判定区域D内f不恒为0  若对很多个随机产生的坐标进行测试，结果次 次均为0，则可说f≠0的概率是非常小 ◼ 有不少问题，目前只有效率很差的确定性求解 算法， 但用随机算法去求解，可以很快地获 得相当可信的结果 3

随机算法的基本概念 随机算法 o随机算法是一种使用概率和统计方法在其执行过程 中对于下一计算步骤作出随机选择的算法 ■随机算法的优越性 o对于有些问题:算法简单 对于有些问题:时间复杂性低 o对于有些问题:同时兼有简单和时间复杂性低

随机算法的基本概念 ◼ 随机算法  随机算法是一种使用概率和统计方法在其执行过程 中对于下一计算步骤作出随机选择的算法 ◼ 随机算法的优越性  对于有些问题：算法简单  对于有些问题：时间复杂性低  对于有些问题：同时兼有简单和时间复杂性低 4

随机算法的基本概念 ■随机算法分类 o随机数值算法 Monte Carlo算法 Las Vegas算法 Sherwood算法 随机数值算法 o主要用于数值问题求解 o算法的输出往往是近似解 o近似解的精确度与算法执行时间成正比

随机算法的基本概念 ◼ 随机算法分类  随机数值算法  Monte Carlo算法  Las Vegas算法  Sherwood算法 ◼ 随机数值算法  主要用于数值问题求解  算法的输出往往是近似解  近似解的精确度与算法执行时间成正比 5

随机算法的基本概念 ■随机算法分类 o随机数值算法 Monte Carlo算法 Las Vegas算法 Sherwood算法 Monte Carlo算法 主要用于求解需要准确解的问题 算法可能给出错误解 o获得精确解概率与算法执行时间成正比

随机算法的基本概念 ◼ 随机算法分类  随机数值算法  Monte Carlo算法  Las Vegas算法  Sherwood算法 ◼ Monte Carlo算法  主要用于求解需要准确解的问题  算法可能给出错误解  获得精确解概率与算法执行时间成正比 6

随机算法的基本概念 随机算法分类 o随机数值算法 Monte Carlo算法 Las Vegas算法 Sherwood算法 Las Vegas算法 旦找到一个解,该解一定是正确的 o找到解的概率与算法执行时间成正比 o增加对问题反复求解次数,可是求解无效的概率任 意小

随机算法的基本概念 ◼ 随机算法分类  随机数值算法  Monte Carlo算法  Las Vegas算法  Sherwood算法 ◼ Las Vegas算法  一旦找到一个解, 该解一定是正确的  找到解的概率与算法执行时间成正比  增加对问题反复求解次数, 可是求解无效的概率任 意小 7

随机算法的基本概念 ■随机算法分类 o随机数值算法 Monte Carlo算法 Las Vegas算法 Sherwood算法 Sherwood算法 一定能够求得一个正确解 o确定算法的最坏与平均复杂性差别大时,加入随机 性,即得到 Sherwood算法 o消除最坏行为与特定实例的联系

随机算法的基本概念 ◼ 随机算法分类  随机数值算法  Monte Carlo算法  Las Vegas算法  Sherwood算法 ◼ Sherwood算法  一定能够求得一个正确解  确定算法的最坏与平均复杂性差别大时, 加入随机 性, 即得到Sherwood算法  消除最坏行为与特定实例的联系 8

随机算法的基本概念 随机算法分析的目标 o平均时间复杂性:时间复杂性随机变量的均值 o获得正确解的概率 获得优化解的概率 解的精确度估计

随机算法的基本概念 ◼ 随机算法分析的目标  平均时间复杂性：时间复杂性随机变量的均值  获得正确解的概率  获得优化解的概率  解的精确度估计 9

随机数值算法 计算值 o设有一个半径为r的圆及其外切四边形 o向正方形随机地投掷n个点,设k个点落入圆内 o投掷点落入圆内的概率为(r2)(4r2)=/4. o用k/n逼近4,即kn4,于是(4k)/n 10

随机数值算法 ◼ 计算值  设有一个半径为 r 的圆及其外切四边形  向正方形随机地投掷n个点, 设k个点落入圆内  投掷点落入圆内的概率为 (r 2 )/(4r2 )= /4.  用k/n逼近/4, 即k/n/4, 于是   (4k)/n. 10 r