单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,随机算法简介,计算机理论实验室 蒋威,2009-12-24,Email:Iamjw.xiaochouyu,随机算法简介计算机理论实验室 蒋威,1,概要,研究领域,随机数理论,随机算法概述,简单应用,POJ例题分析,概要研究领域,2,概要,研究领域,随机数理论,随机算法概述,简单应用,POJ例题分析,概要研究领域,3,研究领域,概率论,基本工具,数论,密码学,NP理论,近似算法（随机）,人工智能,遗传算法、模拟褪火,。,研究领域概率论,4,概要,研究领域,随机数理论,随机算法概述,简单应用,POJ例题分析,概要研究领域,5,随机数理论,随机序列的特征,概率相等(均匀随机),不可预测,不可重现,“伪随机”(pseudo-random),根据某种规则生成，这些随机数不是真正随机的，但在一定程度上可以模拟随机数，一般叫做伪随机数。,对于一个随机算法，使用真随机数和伪随机数，得到的结果近似相等。（Andrew Yao）,Google“什么是随机数”后,随机数理论随机序列的特征Google“什么是随机数”后,6,随机数的产生,“真随机数”的产生,电子噪声,噪音放大(AD转化),量子噪声,“测不准原理”,放射性衰变,核放射源放射粒子数,。,电子噪声,量子噪声,随机数的产生“真随机数”的产生电子噪声量子噪声,7,随机数的产生,“伪随机数”的产生,“Any one who considers arithmetical methods of producing random digits is,of course,in a state of sin.”-John von neumann,常用算法,线性同余，延搁的斐波那契算法，逆同余算法，KISS,密码学相关,BBS，Micali-Schnorr，Rabin，,。,线性同余法,随机数的产生“伪随机数”的产生线性同余法,8,随机数的检验,“伪随机数”的检验,拟合优度检验（统计）,2,检验，KS检验,经验检验,检验集：Knuth，Diehard，NIST,谱检验,。,谱检验,随机数的检验“伪随机数”的检验谱检验,9,概要,研究领域,随机数理论,随机算法概述,简单应用,POJ例题分析,概要研究领域,10,随机算法概述,确定型算法 Vs 随机算法,确定型算法：对某个特定输入的每次运行过程是可重复的，运行结果是一样的,.,随机算法：对某个特定输入的每次运行过程是随机的，运行结果也可能是随机的,.,猜想：,P=BPP,随机算法的优势,在运行时间或者空间需求上随机算法比确定型算法往往有较好的改进,随机算法设计简单,随机算法概述确定型算法 Vs 随机算法,11,随机算法概述,随机算法分类,Sherwood算法,Las Vegas算法,Monte Carlo算法,。,赌城摩纳哥蒙特卡洛,随机算法概述随机算法分类赌城摩纳哥蒙特卡洛,12,Sherwood算法,算法特点,确定型算法在最坏情况下的时间复杂度与其在平均情况下的时间复杂度有较大差异.,引入随机性来消除或减少问题好坏实例之间的这种差别.,精髓不是避免算法的最坏情况发生，而是设法消除这种最坏情形行为与特定实例之间的关联性.,Sherwood算法算法特点,13,Sherwood算法,举例：快速排序,平均复杂度：O(nlogn),最坏复杂度：O(n2),A=(n,n-1,n-2,1)，每次都取A,1,为中位数。,添加随机性后：“随机选择中位数”,在取中位数之前，随机选择一个数A,i,，与A,1,交换。,最坏复杂度:期望为O(nlogn)，达到最坏的概率非常小，可以忽略。,一趟排序前后,Sherwood算法举例：快速排序 一趟排序前后,14,Las Vegas算法,算法特点,对于找不到有效算法的某些问题，可使用Las Vegas算法来求解，可能会很快找到问题的一个解。,一旦得到问题的一个解，一定是正确的。但是，这种算法所作随机性决策可能导致找不到解。,可通过多次调用同一Las Vegas算法来增加得到问题解的概率。,Las Vegas算法算法特点,15,N皇后问题,举例：n皇后问题,在n*n的棋盘上放置n个皇后,皇后之间不会互相攻击,给出一个解法,“8皇后”问题,N皇后问题举例：n皇后问题 “8皇后”问题,16,N皇后问题,随机“爬山法”,局部极大值 Vs 全局最优值,随机重新开始,完备性接近1,对于3,000,000个皇后，可在1分钟以内找到解,喜马拉雅山脉,N皇后问题随机“爬山法”喜马拉雅山脉,17,Monte Carlo算法,算法特点,确定性算法还是随机算法都无法保证每次得到正确的解,Monte Carlo算法以高概率给出正确解,通常无法判定一个具体解是否正确。,可通过重复调用同一个Monte Carlo算法多次来提高获得正确解的概率。,轮盘赌,Monte Carlo算法算法特点轮盘赌,18,主元素问题,举例：主元素问题,定义：数列中，是否有出现次数超过一半的元素。,算法：随机选择一个数，扫描出现次数。若超过一半，输出“YES”，否则输出“NO”。,分析：算法时间复杂度为O(n)。正确的概率1/2。数次调用，可使得正确概率接近1。,有确定型O(n)的算法,主元素问题举例：主元素问题,19,素数测试,举例：素数测试,Miller-Rabin随机测试,基于两个定理：,Fermat小定理：如果n是素数，则对于所有不是n倍数的a，有a,n-1,1(mod n),如果n为素数，则方程x,2,1(mod n)的根只有两个(1),过程：假设n-1=2,r,s，随机产生a，依次考察,a,s,mod n,a,2s,mod n,a,n-1,mod n，,该序列必定以1结束，而且在第一次出现1之前的值必定是n-1。,每次测试失败的概率小于1/4。,多次重复可以极大概率得到正确解。,素数测试举例：素数测试,20,素数测试,Millar-Rabin算法程序框架:,Miller-Rabin算法，摘自刘汝佳,算法艺术与信息学竞赛,素数测试Millar-Rabin算法程序框架:Miller-,21,Monte Carlo算法,其他应用,测试串相等(通信纠错),模式匹配,随机抽样,量子通信示意,Monte Carlo算法其他应用量子通信示意,22,几类算法的比较,几种算法的比较,几类算法的比较几种算法的比较,23,概要,研究领域,随机数理论,随机算法概述,简单应用,POJ例题分析,概要研究领域,24,简单应用,求,值,随机投点法,在正方形中随机投点，统计落入圆中的概率,设n为落入圆的概率，m为试验次数，那么,4n/m,利用切尔诺夫界，可知,Pr(|,4n/m,-,|,)2e,-m,2,/12,投点法,简单应用求值投点法,25,简单应用,洗牌,多种洗牌算法,常见的一种算法：,保证每个位置出现任何一张牌的概率均相等,1 n,lengthA,2,for,i,1,to,n,3,do,swap Ai,ARandom(1,n),发哥与华仔,简单应用洗牌1 n lengthA发哥与华仔,26,简单应用,s-t连通性算法,无向图G=(V,E),s,t为G上两点。令n=|V|，m=|E|。希望确定是否存在一条连接s和t的路。,随机算法：从s开始随机游动，如果在4n,3,步之内到达t，则返回存在一条路；否则，返回不存在路。,算法以1/2的概率返回正确结果。,S到T有路吗？,简单应用s-t连通性算法S到T有路吗？,27,简单应用,最小割随机算法,无向图G=(V，E)中找最小边割集。,算法：每次随机选一条边，合并该边对应的顶点。重复该过程n-2次。最后剩下两点之间的边，就是一个割集。,此方法至少以2/n(n-1)的概率输出最小割集。,重复上述方法n(n-1)lnn次，输出不是一个割集的概率,1/n,2,。,简单应用最小割随机算法,28,概要,研究领域,随机数理论,随机算法概述,简单应用,POJ例题分析,概要研究领域,29,POJ例题分析,POJ 3318,给出3个n*n（n500）的矩阵A，B，C，验证A*B=C?,n3算法会超时。,n2的概率算法：,随机置换法则：如果比特向量a,b,r为随机向量，那么,Pr(a,r),(b,r)1/2,随机一个1*n的向量r，验证A*B*r=C*r，若成立，输出,“YES”，否则输出“NO”。,如果A*B,C，算法以1/2的概率输出“NO”！,POJ例题分析POJ 3318,30,POJ例题分析,POJ2576,有一堆数，需要分为两堆。要求两堆之间元素个数差不超过1，并且两堆和的差值尽量小。（元素个数100,元素值 450）,动态规划可以解决。,随机算法如下：,1.计算两堆的大小后，随机分为两堆。,2.随机选择两堆中的数，如果交换后差变小，则交换。,3.重复2，直到多次交换未发生。更新答案。,4.回到1，重新开始。,POJ例题分析POJ2576,31,其它POJ参考题,在,Donald E.Knuth，计算机程序设计艺术第3版第2卷，清华大学出版社(影印版)，2002年。,2.史道济（译），（哈佛大学&布朗大学）概率与计算，随机算法与概率分析，机械工业出版社，2007年。,3.刘汝佳，黄亮，算法艺术与信息学竞赛，清华大学出版社，2004年。,4.屈婉玲，概率算法课件，北京大学,5.陈卫东，随机算法简介课件，华南师范大学,推荐书目,1.Donald E.Knuth，计算机程序设计艺术第3版第2卷，2002年，清华大学出版社(影印版),2.史道济（译），（哈佛大学&布朗大学）概率与计算，随机算法与概率分析，机械工业出版社，2007年。,3.刘汝佳，黄亮，算法艺术与信息学竞赛，清华大学出版社，2004年。,4.Thomas H.Cormen等，算法导论，第二版，高等教育出版社（影印版），2002年。,5.杨波，现代密码学，第二版，清华大学出版社，2007年。,引用和推荐书目引用文献,33,谢谢大家！,谢谢大家！,34,