随机算法的基本概念 ■随机算法分类 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