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

1、并行算法的设计与分析,第 18 章 随机算法,18.1 随机算法的基本知识,18.1.1 概率论的基本知识 18.1.2 随机算法的概念、模型及其度量 1. 随机算法的概念 定义: 是一个概率图灵机. 也就是在算法中引入随机因素, 即通过随机数选择算法的下一步操作. 三要素: 输入实例、随机源和停止准则. 特点: 简单、快速、易于并行化. 一种平衡: 随机算法可以理解为在时间、空间和随机三大 计算资源中的平衡 (Lu C.J. , Ph.D Thesis , 1999). 重要文献 Motwani R. , Raghavan P. Randomized Algorithms. Cambridg

2、e University Press, New York, 1995,18.1 随机算法的基本知识,18.1.2 随机算法的概念、模型及其度量 2. 随机算法的意义 求解问题的一种重要让步策略：对某些问题，若要求其精确解，则设计出的算法的时间复杂度为指数级增长的，这样的算法在现实中不可行的。 有效的随机算法 实际可行的随机算法 可转化为确定算法 易于并行化 促进智能计算的发展,18.1 随机算法的基本知识,18.1.2 随机算法的概念、模型及其度量 3. 随机算法的重要应用 Monte Carlo求定积分法. 随机k-选择算法. 随机快排序算法 素数判定的随机算法 二阶段随机路由算法. 4.

3、研究随机算法的重要人物及其工作 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)，

4、n为输入长度，以确保每个数据均能存储在一个存储单元中并可在O(1)顺序实现步内执行操作。 假定p个处理器在同一时间步所产生的p个随机数彼此独立。 6. 随机算法的分类 Las Vegas算法和Monte Carlo算法是常见的两类随机算法。 Las Vegas算法运行结束时总能给出正确解，但其运行时间每次有所不同。 Monte Carlo算法每次运行结束时可能得到不正确的结果，但这种概率是很小的且有界。,18.1 随机算法的基本知识,18.1.2 随机算法的概念、模型及其度量 7. 时间复杂性度量 运行时间的期望 实例的运行时间期望 对固定实例x, 设随机算法A的运行时间 是一个0,+)上的随

5、机变量, 定义随机算法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) 将不同的算法组成算法群, 根据输

6、入实例的不同，随机地或有选择地选取不同的算法, 以使性能达到最佳. 2.随机采样法(Random Sampling) 用“小”样本群的信息, 指导整体的求解. 3.随机搜索法(Random Search) 随机地在某个区域进行搜索，这种方法 可以从统计角度分析算法的平均性能, 如果将搜索限制在有解或有较多解的区域, 可以大大提高搜索的成功概率. 4.指印技术(Fingerprinting) 定义指印函数（Hash函数），利用指印信息可以大大减少对象识别的工作量. 例如：通过随机映射的取指印方法, Karp和Rabin设计了一个线性时间复杂度的快速的串匹配随机算法. 5.输入随机重组法(Inpu

7、t Randomization) 对输入实例进行随机重组之后, 可以改进算法的平均性能，例如：随机Quick排序算法.,18.1 随机算法的基本知识,18.1.3 随机算法的设计方法 6. 负载平衡法(Load Balancing) 在并行与分布计算、网络通讯等问题中, 使用随机选择技术分配数据可以达到任务的负载平衡和网络通讯的平衡. 7. 快速混合Markov链法(Rapidly Mixing Markov Chain) 使用该方法可以解决大空间中的均匀抽样问题. 8. 孤立和破对称技术(Isolation and Symmetry Breaking) 使用该技术可以解决内在顺序处理问题的并

8、行性, 避免分布式系统的死锁等问题. 如: 图着色算法, 部分独立集问题 9. 概率存在性证明法(Probabilistic Methods and Existence Proofs) 如果随机选取的物体具有某种特性的概率大于0, 则具有该特性的物体一 定存在. 10. 消除随机性方法(Derandomization) 注：许多优秀的确定性算法均是由随机算法转换而来.,18.6 随机排序,18.6.1 随机采样与随机Quick排序 1. 随机采样 非复原采样法（Sampling without replacement） 等概率地每次从规模为n的原始数据中选择一个元素，选中的元素从原始数据中移去

9、。 复原采样法（Sampling with replacement） 等概率地每次从规模为n的原始数据中选择一个元素，但选中的元素并不从原始数据中移去，即一个元素可能被选择若干次。 2. 随机Quick排序算法 Quick排序算法随机化思想：修改算法的数据划分过程，在Quick排序算法的每一步，当数组还没有被划分时，将元素Ap与从Apr中随机挑选出的一个元素交换，以确保枢点元素x=Ap取自Apr中r-p+1个元素任一个的可能性相同。 经过这样的随机化处理之后，就能期望对输入数组的划分一般都是对称（左、右两部分的数据个数相同）的。,18.6 随机排序,18.6.2 并行随机Quick排序算法 设

10、A是由n个互不相同元素组成的无序数组，算法思想： 从A中随机挑选一个划分元素（Splitter）S(A)，将S(A)与A中各个元素比较，将比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 so

11、rt A using any sorting algorithm and return sorted A; (2) select a random element S(A) from A; / 随机选择一个划分元素 (3) for i=1 to n do in parallel if 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 wit

12、h marked 0; set k equal to position of the element S(A); (5) Randomized-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/

13、 7 (n /30) 次不成功划分步的概率为O(n-7). 定理18.15 算法18.15高概率地可在O(log2n )时间内使用O(nlogn )次操作（工作量），完成对n 个数据的排序 。 RPRAM-EREW上随机并行Quick排序示例 输入：=4, 16, -5, 7, 25, -8, 1, 3, n=8 / 设算法递归到n=1 4, 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

14、, 3, 4 , 7 , 16 , 25,18.6 随机排序,18.6.3 拓展的并行随机Quick排序算法 算法思想：从当前子序列（桶）中随机挑选 个划分元素（样本），将每个桶划分成 +1个较小的桶，然后并行递归排序各个桶。每个划分步的代价仍保持为对数时间，且总的运行时间也是对数的。 算法18.6 RPRAM-EREW上扩展的算法Randomized-Quicksort(A1.n) 输入：待排序的数组，|A|=N输出：有序数组 Begin (1) 若 n 30 则使用任一算法排序 A ; (2) 从A中独立（随机）地采样 n1/2 个划分元素，并形成集合S; (3) 成对比较S中元素将其排序

15、，并以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 随机串匹配,18.7.1 KARP-RABIN串匹配随机算法思想 基于映射思想和素数理论，定义一

16、个称为“指印”(Fingerprint)的函数，它首先将模式串映射成一个比模式串短得多的指印（位串数据），然后将正文串中每一个长度为m 的子串也映射一个比子串本身短得多的指印（位串数据）。要求所构造的指印函数尽可能扫描整个文本串，并且能迅速计算出每个长度为m的子串的指印。 算法的匹配比较过程不是直接比较模式串与正文子串本身，而是比较模式串的指印函数值和正文子串的指印函数值。 若两者的指印函数值相等，算法就认为模式与当前正文子串高概率地匹配。 假设正文串与模式串中出现的字符集合为，= d。将模式串以及正文串中每个长度为m的子串用以d为基的整数表示 。即定义一个映射（函数），它将长度为m 的字符串

17、映射成整数x(0 xd-1)。,18.7 随机串匹配,18.7.2 KARP-RABIN串匹配随机算法 设asc(c)为字符c 的ASCII值，将模式串P = p1p2pm 表示成: x = asc(p1)dm-1 + asc(p2)dm-2 + + asc(pm-1)d1+ asc(pm) 其对应的指印（散列）函数是： h(x) = x mod q， q是区间 1, n2 m 中随机选取的某个适当大的素数。 同理，将正文串中长度为m 的某个子串titi+1 ti+m-1 表示成: y = asc(ti)dm-1 + asc(ti+1)dm-2 + + asc(ti+m-2)d1 + asc(

18、ti+m-1) 其对应的指印（散列）函数是： h(y)= y mod q，q是区间 1, n2 m 中随机选取的某个适当大的素数。 为了迅速计算出正文中每个长度为m的字符串的指印（散列）函数值，我们考虑正文中前后两个紧接着的长度为m的字符串的指印函数值之间的关系。 记正文中子串titi+1 ti+m-1对应的整数为yi ，则有 yi = asc(ti)dm-1 + asc(ti+1)dm-2 + + asc(ti+m-2)d1 + asc(ti+m-1) 而正文中子串ti+1 ti+2 ti+m 对应的整数为yi+1 满足 yi+1 = asc(ti+1)dm-1 + asc(ti+2)dm-2 + + asc(ti+m-1)d1 + asc(ti+m) = (yi asc (ti ) dm-1)d + asc(ti+m ) 因此有: h(yi+1) = h (yi asc (ti ) dm-1)d + asc(ti+m ) ) mod q ，