并行算法的设计与分析().PPT

并行算法的设计与分析 第 18 章 随机算法 18.1 随机算法的基本知识 18.1.1 概率论的基本知识 18.1.2 随机算法的概念、模型及其度量 1. 随机算法的概念 定义: 是一个概率图灵机. 也就是在算法中引入随机因素, 即通过随机数选择算法的下一步操作. 三要素: 输入实例、随机源和停止准则. 特点: 简单、快速、易于并行化. 一种平衡: 随机算法可以理解为在时间、空间和随机三大 计算资源中的平衡 (Lu C.J. , Ph.D Thesis , 1999). 重要文献 Motwani R. , Raghavan P. Randomized Algorithms. Cambridge University Press, New York, 1995 18.1 随机算法的基本知识 18.1.2 随机算法的概念、模型及其度量 2. 随机算法的意义 求解问题的一种重要让步策略：对某些问题，若要求其精确解，则设计出的算法的时间复杂度为指数级增长的，这样的算法在现实中不可行的。 有效的随机算法 实际可行的随机算法 可转化为确定算法 易于并行化 促进智能计算的发展 18.1 随机算法的基本知识 18.1.2 随机算法的概念、模型及其度量 3. 随机算法的重要应用 Monte Carlo求定积分法. 随机k-选择算法. 随机快排序算法 素数判定的随机算法 二阶段随机路由算法. 4. 研究随机算法的重要人物及其工作 de Leeuw等人提出了概率图灵机(1955) John Gill的随机算法复杂性理论(1977) Rabin的数论和计算几何领域的工作(1976) Karp的算法概率分析方法(1985) Shor的大数素因子分解量子计算算法(1994) 18.1 随机算法的基本知识 18.1.2 随机算法的概念、模型及其度量 5.随机算法计算模型—随机PRAM模型（Randomized PRAM Model, RPRAM) 允许每个处理器在单步时间内产生某个范围的随机数。一个随机数在整数区间[1,2,…,m]内均等地取任一整数值。 限定在单步时间内产生的随机数的位数为O(logn)，n为输入长度，以确保每个数据均能存储在一个存储单元中并可在O(1)顺序实现步内执行操作。 假定p个处理器在同一时间步所产生的p个随机数彼此独立。 6. 随机算法的分类 Las Vegas算法和Monte Carlo算法是常见的两类随机算法。 Las Vegas算法运行结束时总能给出正确解，但其运行时间每次有所不同。 Monte Carlo算法每次运行结束时可能得到不正确的结果，但这种概率是很小的且有界。 18.1 随机算法的基本知识 18.1.2 随机算法的概念、模型及其度量 7. 时间复杂性度量 运行时间的期望 实例的运行时间期望 对固定实例x, 设随机算法A的运行时间 是一个[0,+∞)上的随机变量, 定义随机算法A在实例x上的运行时间期望为E[ ] , 也称为随机算法A在实例x上的执行时间. 算法的运行时间期望 如果对一个规模为n的问题的所有实例是均匀选取的, 则定义各个实例上 的平均执行时间为随机算法在该问题上的运行时间期望, 记为T(n) 随机复杂度类(参见Motwani R., Raghavan P., Randomized Algorithms.) RP(Randomized Polynomial time), etc. 18.1 随机算法的基本知识 18.1.3 随机算法的设计方法 1.挫败对手法(Foiling the Adversary) 将不同的算法组成算法群, 根据输入实例的不同，随机地或有选择地选取不同的算法, 以使性能达到最佳. 2.随机采样法(Random Sampling) 用“小”样本群的信息, 指导整体的求解. 3.随机搜索法(Random Search) 随机地在某个区域进行搜索，这种方法 可以从统计角度分析算法的平均性能, 如果将搜索限制在有解或有较多解的区域, 可以大大提高搜索的成功概率. 4.指印技术(Fingerprinting) 定义指印函数（Hash函数），利用指印信息可以大大减少对象识别的工作量. 例如：通过随机映射的取指印方法, Karp和Rabin设计了一个线性时间复杂度的快速的串匹配随机算法. 5.输入随机重组法(Input Randomization) 对输入实例进行随机重组之后, 可以改进算法的平均性能，例如：随