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