《并行算法的设计与分析(18)》由会员分享，可在线阅读，更多相关《并行算法的设计与分析(18)（15页珍藏版）》请在金锄头文库上搜索。
1、并行算法的设计与分析第 18 章 随机算法18.1 随机算法的基本知识18.1.1 概率论的基本知识18.1.2 随机算法的概念、模型及其度量 1. 随机算法的概念 n 定义: 是一个概率图灵机. 也就是在算法中引入随机因素, 即通过随机数选择算法的下一步操作. n 三要素: 输入实例、随机源和停止准则. n 特点: 简单、快速、易于并行化. n 一种平衡: 随机算法可以理解为在时间、空间和随机三大计算资源中的平衡 (Lu C.J. , Ph.D Thesis , 1999). n 重要文献MotwaniMotwani R. R. , , RaghavanRaghavan P. Randomi
2、zed Algorithms. P. Randomized Algorithms.Cambridge University Press, New York, 1995 Cambridge University Press, New York, 199518.1 随机算法的基本知识18.1.2 随机算法的概念、模型及其度量2. 随机算法的意义 n 求解问题的一种重要让步策略：对某些问题，若要求其精确解，则设计 出的算法的时间复杂度为指数级增长的，这样的算法在现实中不可行的 。n 有效的随机算法n 实际可行的随机算法n 可转化为确定算法n 易于并行化n 促进智能计算的发展18.1 随机算法的基本知
3、识18.1.2 随机算法的概念、模型及其度量 3. 随机算法的重要应用 n Monte Carlo求定积分法. n 随机k-选择算法.n 随机快排序算法 n 素数判定的随机算法 n 二阶段随机路由算法. 4. 研究随机算法的重要人物及其工作 n de Leeuw等人提出了概率图灵机(1955) n John Gill的随机算法复杂性理论(1977) n Rabin的数论和计算几何领域的工作(1976) n Karp的算法概率分析方法(1985) n Shor的大数素因子分解量子计算算法(1994)18.1 随机算法的基本知识18.1.2 随机算法的概念、模型及其度量5.随机算法计算模型随机PR
4、AM模型（Randomized PRAM Model, RPRAM)n 允许每个处理器在单步时间内产生某个范围的随机数。一个随机数在整 数区间1,2,m内均等地取任一整数值。 n 限定在单步时间内产生的随机数的位数为O(logn)，n为输入长度，以确保 每个数据均能存储在一个存储单元中并可在O(1)顺序实现步内执行操作。 n 假定p个处理器在同一时间步所产生的p个随机数彼此独立。6. 随机算法的分类 n Las Vegas算法和Monte Carlo算法是常见的两类随机算法。 Las Vegas算法运行结束时总能给出正确解，但其运行时间每次有所不同 。 Monte Carlo算法每次运行结束时
5、可能得到不正确的结果，但这种概率是 很小的且有界。18.1 随机算法的基本知识18.1.2 随机算法的概念、模型及其度量7. 时间复杂性度量n 运行时间的期望 实例的运行时间期望对固定实例x, 设随机算法A的运行时间 是一个0,+)上的随机变量,定义随机算法A在实例x上的运行时间期望为E , 也称为随机算法A在实 例x上的执行时间. 算法的运行时间期望如果对一个规模为n的问题的所有实例是均匀选取的, 则定义各个实例上的平均执行时间为随机算法在该问题上的运行时间期望, 记为T(n)n 随机复杂度类(参见MotwaniMotwani R., R., RaghavanRaghavan P., Ran
6、domized P., Randomized Algorithms.Algorithms.)RP(Randomized Polynomial time), etc.18.1 随机算法的基本知识18.1.3 随机算法的设计方法 1.挫败对手法(Foiling the AdversaryFoiling the Adversary)将不同的算法组成算法群, 根据输入实例的不同，随机地或有选择地选取不同的算法 , 以使性能达到最佳. 2.随机采样法(Random SamplingRandom Sampling) 用“小”样本群的信息, 指导整体的求解. 3.随机搜索法(Random SearchRan
7、dom Search)随机地在某个区域进行搜索，这种方法 可以从统计角度分析算法的平均性能, 如果 将搜索限制在有解或有较多解的区域, 可以大大提高搜索的成功概率. 4.指印技术(FingerprintingFingerprinting)定义指印函数（Hash函数），利用指印信息可以大大减少对象识别的工作量. 例如 ：通过随机映射的取指印方法, Karp和Rabin设计了一个线性时间复杂度的快速的串 匹配随机算法. 5.输入随机重组法(Input RandomizationInput Randomization)对输入实例进行随机重组之后, 可以改进算法的平均性能，例如：随机Quick排序算法
8、 .18.1 随机算法的基本知识18.1.3 随机算法的设计方法 6. 负载平衡法(Load Balancing)在并行与分布计算、网络通讯等问题中, 使用随机选择技术分配数据可以达 到任务的负载平衡和网络通讯的平衡. 7. 快速混合Markov链法(Rapidly Mixing Markov Chain) 使用该方法可以解决大空间中的均匀抽样问题. 8. 孤立和破对称技术(Isolation and Symmetry Breaking)使用该技术可以解决内在顺序处理问题的并行性, 避免分布式系统的死锁等 问题. 如: 图着色算法, 部分独立集问题 9. 概率存在性证明法(Probabilis
9、tic Methods and Existence Proofs)如果随机选取的物体具有某种特性的概率大于0, 则具有该特性的物体一定存在. 10. 消除随机性方法(Derandomization)注：许多优秀的确定性算法均是由随机算法转换而来.18.6 随机排序18.6.1 随机采样与随机Quick排序 1. 随机采样 非复原采样法（Sampling without replacement）等概率地每次从规模为n的原始数据中选择一个元素，选中的元素从原始数据中移 去。 复原采样法（Sampling with replacement）等概率地每次从规模为n的原始数据中选择一个元素，但选中的元素
10、并不从原始数 据中移去，即一个元素可能被选择若干次。2. 随机Quick排序算法Quick排序算法随机化思想：修改算法的数据划分过程，在Quick排序算法 的每一步，当数组还没有被划分时，将元素Ap与从Apr中随机挑选出 的一个元素交换，以确保枢点元素x=Ap取自Apr中r-p+1个元素任一个 的可能性相同。经过这样的随机化处理之后，就能期望对输入数组的划分一般都是对称（ 左、右两部分的数据个数相同）的。 18.6 随机排序18.6.2 并行随机Quick排序算法设A是由n个互不相同元素组成的无序数组，算法思想： 从A中随机挑选一个划分元素（Splitter）S(A)，将S(A)与A中各个元素
11、比较，将比 S(A)小的元素标记为1，比S(A)大的元素标记为0； 将较小的元素移向A的前端，而将较大的元素移向的后端; 对于这些较小的元素（子序列，桶）和较大的元素（子序列，桶） 重复以上相同 的策略进行并行处理，直到子序列（ 桶）中的元素数足够小(如30)为止。算法18.5 RPRAM-EREW上随机Quick排序算法Randomized-Quicksort(A1.n)输入：待排序的数组，|A|=n 输出：有序数组Begin(1) if n=30 the sort A using any sorting algorithm and return sorted A; (2) select a
12、 random element S(A) from A; / 随机选择一个划分元素(3) for i=1 to n do in parallelif Ai S(A) then marki=1 else marki=0; (4) compact the elements of A with marked 1 at beginning of A, followed by S(A) which is followed by the elements of A with marked 0; set k equal to position of the element S(A);(5) Randomiz
13、ed-Quicksort(A1.k-1); / 并行递归调用Randomized-Quicksort(Ak+1.n)End.18.6 随机排序18.6.2 并行随机Quick排序算法设e是中的任一元素，nj为第j（ j 1）次划分结束时，包含的子序列（ 桶）的容量（元素数目），其中n0n，则 引理18.8 对于任意的j 0，Prnj+1 7nj/8 1/4. 引理18.9 在20log8/7n次划分步中，元素e 经历了20log8/7n -log8/ 7 (n /30) 次不成功划分步的概率为O(n-7). 定理18.15 算法18.15高概率地可在O(log2n )时间内使用O(nlogn
14、)次 操作（工作量），完成对n 个数据的排序 。 RPRAM-EREW上随机并行Quick排序示例输入：=4, 16, -5, 7, 25, -8, 1, 3, n=8 / 设算法递归到n=14, 16, -5, 7, 25, -8, 1, 3 4, -5, -8, 1, 3 , 7 , 16 , 25 -8 , -5, 4, 1, 3 , 7 , 16 , 25 -8 , -5, 1, 3 , 4 , 7 , 16 , 25 -8 , -5, 1, 3, 4 , 7 , 16 , 2518.6 随机排序18.6.3 拓展的并行随机Quick排序算法算法思想：从当前子序列（桶）中随机挑选 个划
15、分元素（样本），将每个桶 划分成 +1个较小的桶，然后并行递归排序各个桶。每个划分步的代价仍保持 为对数时间，且总的运行时间也是对数的。 算法18.6 RPRAM-EREW上扩展的算法Randomized-Quicksort(A1.n)输入：待排序的数组，|A|=N 输出：有序数组Begin(1) 若 n 30 则使用任一算法排序 A ; (2) 从A中独立（随机）地采样 n1/2 个划分元素，并形成集合S; (3) 成对比较S中元素将其排序，并以n1/2 * n1/2 的二维表T 的形式存放结果; 对T 的每一行用前缀和计算S 各元素的位序；(4) 将 A 中元素置入桶Bi，1 i n1/2 +1, 使得Bi 的元素就是A 中那些处 于S 中 第(i -1)个最小者和第i 个最小者之间的元素; / 第0个最小者为负无穷大，第 +1个最小者为正无穷大 (5) 并行递归排序各桶中的元素End. 定理18.16 算法18.15高概率地可在O(logn )时间内使用O(nlogn )次操作（工作量） ，完成对n 个数据的排序 。18.7 随机串匹配n 18.7.1 KARP-RABIN串匹配随机算法思想基于映射思想和素数理论，定义一个称为“指印”(Fingerprint)的函数，它 首先将模式串映射成一个比模式串短得多的指印（位串数据），然后将 正文串中每一个长度为m 的
