随机算法 概要课件

随机算法简介计算机理论实验室蒋威2009-12-24Email:Iamjw.xiaochouyu@随机算法简介计算机理论实验室蒋威1概要研究领域随机数理论随机算法概述简单应用POJ例题分析概要研究领域2概要研究领域随机数理论随机算法概述简单应用POJ例题分析概要研究领域3研究领域概率论基本工具数论密码学NP理论近似算法（随机）人工智能遗传算法、模拟褪火。。。研究领域概率论4概要研究领域随机数理论随机算法概述简单应用POJ例题分析概要研究领域5随机数理论随机序列的特征概率相等(均匀随机)不可预测不可重现“伪随机”(pseudo-random)根据某种规则生成，这些随机数不是真正随机的，但在一定程度上可以模拟随机数，一般叫做伪随机数。对于一个随机算法，使用真随机数和伪随机数，得到的结果近似相等。（AndrewYao）Google“什么是随机数”后…随机数理论随机序列的特征Google“什么是随机数”后…6随机数的产生“真随机数”的产生电子噪声噪音放大(AD转化)量子噪声“测不准原理”放射性衰变核放射源放射粒子数。。。电子噪声量子噪声随机数的产生“真随机数”的产生电子噪声量子噪声7随机数的产生“伪随机数”的产生“Anyonewhoconsidersarithmeticalmethodsofproducingrandomdigitsis,ofcourse,inastateofsin.”---Johnvonneumann常用算法线性同余，延搁的斐波那契算法，逆同余算法，KISS…密码学相关BBS，Micali-Schnorr，Rabin，…。。。线性同余法随机数的产生“伪随机数”的产生线性同余法8随机数的检验“伪随机数”的检验拟合优度检验（统计）χ2检验，KS检验经验检验检验集：Knuth，Diehard，NIST谱检验。。。谱检验随机数的检验“伪随机数”的检验谱检验9概要研究领域随机数理论随机算法概述简单应用POJ例题分析概要研究领域10随机算法概述确定型算法Vs随机算法确定型算法：对某个特定输入的每次运行过程是可重复的，运行结果是一样的.随机算法：对某个特定输入的每次运行过程是随机的，运行结果也可能是随机的.猜想：P=BPP随机算法的优势在运行时间或者空间需求上随机算法比确定型算法往往有较好的改进随机算法设计简单随机算法概述确定型算法Vs随机算法11随机算法概述随机算法分类Sherwood算法LasVegas算法MonteCarlo算法。。。赌城——摩纳哥蒙特卡洛随机算法概述随机算法分类赌城——摩纳哥蒙特卡洛12Sherwood算法算法特点确定型算法在最坏情况下的时间复杂度与其在平均情况下的时间复杂度有较大差异.引入随机性来消除或减少问题好坏实例之间的这种差别.精髓不是避免算法的最坏情况发生，而是设法消除这种最坏情形行为与特定实例之间的关联性.Sherwood算法算法特点13Sherwood算法举例：快速排序平均复杂度：O(nlogn)最坏复杂度：O(n^2)A=(n,n-1,n-2,…,1)，每次都取A1为中位数。添加随机性后：“随机选择中位数”在取中位数之前，随机选择一个数Ai，与A1交换。最坏复杂度:期望为O(nlogn)，达到最坏的概率非常小，可以忽略。一趟排序前后Sherwood算法举例：快速排序一趟排序前后14LasVegas算法算法特点对于找不到有效算法的某些问题，可使用LasVegas算法来求解，可能会很快找到问题的一个解。一旦得到问题的一个解，一定是正确的。但是，这种算法所作随机性决策可能导致找不到解。可通过多次调用同一LasVegas算法来增加得到问题解的概率。LasVegas算法算法特点15N皇后问题举例：n皇后问题在n*n的棋盘上放置n个皇后皇后之间不会互相攻击给出一个解法“8皇后”问题N皇后问题举例：n皇后问题“8皇后”问题16N皇后问题随机“爬山法”局部极大值Vs全局最优值随机重新开始完备性接近1对于3,000,000个皇后，可在1分钟以内找到解喜马拉雅山脉N皇后问题随机“爬山法”喜马拉雅山脉17MonteCarlo算法算法特点确定性算法还是随机算法都无法保证每次得到正确的解MonteCarlo算法以高概率给出正确解通常无法判定一个具体解是否正确。可通过重复调用同一个MonteCarlo算法多次来提高获得正确解的概率。轮盘赌MonteCarlo算法算法特点轮盘赌18主元素问题举例：主元素问题定义：数列中，是否有出现次数超过一半的元素。算法：随机选择一个数，扫描出现次数。若超过一半，输出“YES”，否则输出“NO”。分析：算法时间复杂度为O(n)。正确的概率>1/2。数次调用，可使得正确概率接近1。有确定型O(n)的算法主元素问题举例：主元素问题19素数测试举例：素数测试Miller-Rabin随机测试基于两个定理：Fermat小定理：如果n是素数，则对于所有不是n倍数的a，有an-1≡1(modn)如果n为素数，则方程x2≡1(modn)的根只有两个(±1)过程：假设n-1=2rs，随机产生a，依次考察 asmodn,a2smodn,…,an-1modn，该序列必定以1结束，而且在第一次出现1之前的值必定是n-1。每次测试失败的概率小于1/4。多次重复可以极大概率得到正确解。素数测试举例：素数测试20素数测试Millar-Rabin算法程序框架:Miller-Rabin算法，摘自刘汝佳《算法艺术与信息学竞赛》素数测试Millar-Rabin算法程序框架:Miller-21MonteCarlo算法其他应用测试串相等(通信纠错)模式匹配随机抽样……量子通信示意MonteCarlo算法其他应用量子通信示意22几类算法的比较几种算法的比较几类算法的比较几种算法的比较23概要研究领域随机数理论随机算法概述简单应用POJ例题分析概要研究领域24简单应用求π值随机投点法在正方形中随机投点，统计落入圆中的概率设n为落入圆的概率，m为试验次数，那么

Π≈4n/m利用切尔诺夫界，可知Pr(|4n/m-Π|≥εΠ)<2e-mΠε2/12投点法简单应用求π值投点法25简单应用洗牌多种洗牌算法常见的一种算法：保证每个位置出现任何一张牌的概率均相等1nlength[A]2fori1ton3doswapA[i]A[Random(1,n)]发哥与华仔简单应用洗牌1nlength[A]发哥与华仔26简单应用s-t连通性算法无向图G=(V,E),s,t为G上两点。令n=|V|，m=|E|。希望确定是否存在一条连接s和t的路。随机算法：从s开始随机游动，如果在4n3步之内到达t，则返回存在一条路；否则，返回不存在路。算法以1/2的概率返回正确结果。S到T有路吗？简单应用s-t连通性算法S到T有路吗？27简单应用最小割随机算法无向图G=(V，E)中找最小边割集。算法：每次随机选一条边，合并该边对应的顶点。重复该过程n-2次。最后剩下两点之间的边，就是一个割集。此方法至少以2/n(n-1)的概率输出最小割集。重复上述方法n(n-1)lnn次，输出不是一个割集的概率≤1/n2。简单应用最小割随机算法28概要研究领域随机数理论随机算法概述简单应用POJ例题分析概要研究领域29POJ例题分析POJ3318给出3个n*n（n≤500）的矩阵A，B，C，验证A*B=C?n^3算法会超时。n^2的概率算法：随机置换法则：如果比特向量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例题分析POJ331830POJ例题分析POJ2576有一堆数，需要分为两堆。要求两堆之间元素个数差不超过1，并且两堆和的差值尽量小。（元素个数≤100,元素值≤450）动态规划可以解决。随机算法如下：1.计算两堆的大小后，随机分为两堆。2.随机选择两堆中的数，如果交换后差变小，则交换。3.重复2，直到多次交换未发生。更新答案。4.回到1，重新开始。POJ例题分析POJ257631其它POJ参考题在/JudgeOnline讨论区中直接搜索“随机”......其它POJ参考题32引用和推荐书目引用文献1.DonaldE.Knuth，《计算机程序设计艺术》第3版第2卷，清华大学出版社(影印版)，2002年。2.史道济（译），（哈佛大学&布朗大学）《概率与计算》，随机算法与概率分析，机械工业出版社，2007年。3.刘汝佳，黄亮，《算法艺术与信息学竞赛》，清华大学出版社，2004年。4.屈婉玲，《概率算法》课件，北京大学5.陈卫东，《随机算法简介》课件，华南师范大学推荐书目1.DonaldE.Knuth，《计算机程序设计艺术》第3版第2卷，2002年，清华大学出版社(影印版)2.史道济（译），（哈佛大学&布朗大学）《概率与计算》，随机算法与概率分析，机械工业出版社，2007年。3.刘汝佳，黄亮，《算法艺术与信息学竞赛》，清华大学出版社，2004年。4.ThomasH.Cormen等，《算法导论》，第二版，高等教育出版社（影印版），2002年。5.杨波，《现代密码学》，第二版，清华大学出版社，2007年。引用和推荐书目引用文献33谢谢大家！谢谢大家！34随机算法简介计算机理论实验室蒋威2009-12-24Email:Iamjw.xiaochouyu@随机算法简介计算机理论实验室蒋威35概要研究领域随机数理论随机算法概述简单应用POJ例题分析概要研究领域36概要研究领域随机数理论随机算法概述简单应用POJ例题分析概要研究领域37研究领域概率论基本工具数论密码学NP理论近似算法（随机）人工智能遗传算法、模拟褪火。。。研究领域概率论38概要研究领域随机数理论随机算法概述简单应用POJ例题分析概要研究领域39随机数理论随机序列的特征概率相等(均匀随机)不可预测不可重现“伪随机”(pseudo-random)根据某种规则生成，这些随机数不是真正随机的，但在一定程度上可以模拟随机数，一般叫做伪随机数。对于一个随机算法，使用真随机数和伪随机数，得到的结果近似相等。（AndrewYao）Google“什么是随机数”后…随机数理论随机序列的特征Google“什么是随机数”后…40随机数的产生“真随机数”的产生电子噪声噪音放大(AD转化)量子噪声“测不准原理”放射性衰变核放射源放射粒子数。。。电子噪声量子噪声随机数的产生“真随机数”的产生电子噪声量子噪声41随机数的产生“伪随机数”的产生“Anyonewhoconsidersarithmeticalmethodsofproducingrandomdigitsis,ofcourse,inastateofsin.”---Johnvonneumann常用算法线性同余，延搁的斐波那契算法，逆同余算法，KISS…密码学相关BBS，Micali-Schnorr，Rabin，…。。。线性同余法随机数的产生“伪随机数”的产生线性同余法42随机数的检验“伪随机数”的检验拟合优度检验（统计）χ2检验，KS检验经验检验检验集：Knuth，Diehard，NIST谱检验。。。谱检验随机数的检验“伪随机数”的检验谱检验43概要研究领域随机数理论随机算法概述简单应用POJ例题分析概要研究领域44随机算法概述确定型算法Vs随机算法确定型算法：对某个特定输入的每次运行过程是可重复的，运行结果是一样的.随机算法：对某个特定输入的每次运行过程是随机的，运行结果也可能是随机的.猜想：P=BPP随机算法的优势在运行时间或者空间需求上随机算法比确定型算法往往有较好的改进随机算法设计简单随机算法概述确定型算法Vs随机算法45随机算法概述随机算法分类Sherwood算法LasVegas算法MonteCarlo算法。。。赌城——摩纳哥蒙特卡洛随机算法概述随机算法分类赌城——摩纳哥蒙特卡洛46Sherwood算法算法特点确定型算法在最坏情况下的时间复杂度与其在平均情况下的时间复杂度有较大差异.引入随机性来消除或减少问题好坏实例之间的这种差别.精髓不是避免算法的最坏情况发生，而是设法消除这种最坏情形行为与特定实例之间的关联性.Sherwood算法算法特点47Sherwood算法举例：快速排序平均复杂度：O(nlogn)最坏复杂度：O(n^2)A=(n,n-1,n-2,…,1)，每次都取A1为中位数。添加随机性后：“随机选择中位数”在取中位数之前，随机选择一个数Ai，与A1交换。最坏复杂度:期望为O(nlogn)，达到最坏的概率非常小，可以忽略。一趟排序前后Sherwood算法举例：快速排序一趟排序前后48LasVegas算法算法特点对于找不到有效算法的某些问题，可使用LasVegas算法来求解，可能会很快找到问题的一个解。一旦得到问题的一个解，一定是正确的。但是，这种算法所作随机性决策可能导致找不到解。可通过多次调用同一LasVegas算法来增加得到问题解的概率。LasVegas算法算法特点49N皇后问题举例：n皇后问题在n*n的棋盘上放置n个皇后皇后之间不会互相攻击给出一个解法“8皇后”问题N皇后问题举例：n皇后问题“8皇后”问题50N皇后问题随机“爬山法”局部极大值Vs全局最优值随机重新开始完备性接近1对于3,000,000个皇后，可在1分钟以内找到解喜马拉雅山脉N皇后问题随机“爬山法”喜马拉雅山脉51MonteCarlo算法算法特点确定性算法还是随机算法都无法保证每次得到正确的解MonteCarlo算法以高概率给出正确解通常无法判定一个具体解是否正确。可通过重复调用同一个MonteCarlo算法多次来提高获得正确解的概率。轮盘赌MonteCarlo算法算法特点轮盘赌52主元素问题举例：主元素问题定义：数列中，是否有出现次数超过一半的元素。算法：随机选择一个数，扫描出现次数。若超过一半，输出“YES”，否则输出“NO”。分析：算法时间复杂度为O(n)。正确的概率>1/2。数次调用，可使得正确概率接近1。有确定型O(n)的算法主元素问题举例：主元素问题53素数测试举例：素数测试Miller-Rabin随机测试基于两个定理：Fermat小定理：如果n是素数，则对于所有不是n倍数的a，有an-1≡1(modn)如果n为素数，则方程x2≡1(modn)的根只有两个(±1)过程：假设n-1=2rs，随机产生a，依次考察 asmodn,a2smodn,…,an-1modn，该序列必定以1结束，而且在第一次出现1之前的值必定是n-1。每次测试失败的概率小于1/4。多次重复可以极大概率得到正确解。素数测试举例：素数测试54素数测试Millar-Rabin算法程序框架:Miller-Rabin算法，摘自刘汝佳《算法艺术与信息学竞赛》素数测试Millar-Rabin算法程序框架:Miller-55MonteCarlo算法其他应用测试串相等(通信纠错)模式匹配随机抽样……量子通信示意MonteCarlo算法其他应用量子通信示意56几类算法的比较几种算法的比较几类算法的比较几种算法的比较57概要研究领域随机数理论随机算法概述简单应用POJ例题分析概要研究领域58简单应用求π值随机投点法在正方形中随机投点，统计落入圆中的概率设n为落入圆的概率，m为试验次数，那么

Π≈4n/m利用切尔诺夫界，可知Pr(|4n/m-Π|≥εΠ)<2e-mΠε2/12投点法简单应用求π值投点法59简单应用洗牌多种洗牌算法常见的一种算法：保证每个位置出现任何一张牌的概率均相等1nlength[A]2fori1ton3doswapA[i]A[Random(1,n)]发哥与华仔简单应用洗牌1nlength[A]发哥与华仔60简单应用s-t连通性算法无向图G=(V,E),s,t为G上两点。令n=|V|，m=|E|。希望确定是否存在一条连接s和t的路。随机算法：从s开始随机游动，如果在4n3步之内到达t，则返回存在一条路；否则，返回不存在路。算法以1/2的概率返回正确结果。S到T有路吗？简单应用s-t连通性算法S到T有路吗？61简单应用最小割随机算法无向图G=(V，E)中找最小边割集。算法：每次随机选一条边，合并该边对应的顶点。重复该过程n-2次。最后剩下两点之间的边，就是一个割集。此方法至少以2/n(n-1)的概率输出最小割集。重复上述方法n(n-1)lnn次，输出不是一个割集的概率≤1/n2。简单应用最小割随机算法62概要研究领域随机数理论随机算法概述简单应用POJ例题分析概要研究领域63POJ例题分析POJ3318给出3个n*n（n≤500）的矩阵A，B，C，验证A*B=C?n^3算法会超时。n^2的概率算法：随机置换法则：如果