算法分析与设计课件：随机算法

1、随机算法 2021-9-222 of 158l定义：在算法中引入随机因素, 即通过随机数选择算法的下一步操作。特点：简单、快速一种平衡：随机算法可以理解为在时间、空间和随机三大计算资源中的平衡2021-9-223 of 158计算机产生随机数的方法 d0=d dn=bdn-1+c an= dn % 655362021-9-224 of 1581、数值概率算法：用于数值问题的求解2、Sherwood算法一定能得到问题的正确解常见的四类随机算法：2021-9-225 of 1583、Las Vegas算法或者得到正确的解，或者得不到解。 4、Monte Carlo算法一定能得到解，但是得到的解可能

2、不正确，然而这种概率是小的且有界的。常见的四类随机算法：2021-9-226 of 158一种重要让步策略： 传统算法传统算法: 以以100成功概率求解成功概率求解 确定的确定的 问题的最优解问题的最优解 近似算法近似算法: 一种对解质量的让步一种对解质量的让步算法算法 随机算法随机算法: 一种对求解成功概率和一种对求解成功概率和 非确定的非确定的 解质量的让步解质量的让步 智能算法智能算法: 遗传算法、模拟退火法、遗传算法、模拟退火法、 拟人拟物算法等拟人拟物算法等2021-9-227 of 158设有一半径为设有一半径为r的圆及其外切四边形。向该正方形随机地投掷的圆及其外切四边形。向该正方

3、形随机地投掷n个个点。设落入圆内的点数为点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为因而所投入的点落入圆内的概率为 。所以当。所以当n足够大足够大时，时，k与与n之比就逼近这一概率。从而之比就逼近这一概率。从而 。4422rrnk4double darts(int n) / 用随机投点法计算值 int k=0; for (int i=1;i =n;i+) double x=Random(); double y=Random(); if (x*x+y*y)1是一个整数。关于整数n的因子分解问题是找出n的如下形式的惟

4、一分解式：其中，p1p2pk是k个素数，m1,m2,mk是k个正整数。如果n是一个合数，则n必有一个非平凡因子x，1xn，使得x可以整除n。给定一个合数n，求n的一个非平凡因子的问题称为整数n的因子分割问题。kmkmmpppn2121int split(int n) int m = sqrt(double)n); for (int i=2; i=m; i+) if (n%i=0) return i; return 1; 事实上，算法split(n)是对范围在1x的所有整数进行了试除而得到范围在1x2的任一整数的因子分割。 2021-9-2213 of 158在开始时选取0n-1范围内的随机数，

5、然后递归地由产生无穷序列对于i=2k，以及2kj2k+1，算法计算出xj-xi与n的最大公因子d=gcd(xj-xi，n)。如果d是n的非平凡因子，则实现对n的一次分割，算法输出n的因子d。nxxiimod) 1(21,21kxxxvoid pollard(int n) / 求整数n因子分割的拉斯维加斯算法 int i=1,k=2; int x=random(1, n); y=x; / 随机整数 while (i1) & (dn/2时，称元素x为数组T的主元素。l majority(int t,int n) 随机产生整数i； int x=ti; int k=0; for(int j=1;jn/

6、2); 2021-9-2215 of 158主元素问题lmajority2返回true的概率是p+(1-p)p=1-(1-p)23/4l majority2(int t,int n) if (majority(t,n) return true;else return majority(t,n); 2021-9-2216 of 158主元素问题2021-9-2217 of 158l最小截问题定义： 给定一个无向图G(V,E)，找一个截(V1,V2)使得V1和V2间的连边数最小。2021-9-2218 of 158l随机算法 随机选一条边，将两顶点合一并除去顶点上的环； 直到图中只剩下两个顶点；

7、返回剩下两顶点间的连边数；l重复版本 重复执行算法k次，取返回连边数最小数作为解。2021-9-2219 of 158l示例：#cut=215423541, 234, 51, 234, 51, 2, 3l出错概率 重复k次出错概率为)1(2) 1(21nnkkenn本算法是一个本算法是一个Monte Carlo型算法型算法2021-9-2220 of 158l 素数测试素数测试定理定理1 1 FermatFermat小定理小定理 如果如果n n为素数，则对所有小于为素数，则对所有小于n n的正整数的正整数a a有有 a an-1n-1 1(mod n)1(mod n)检测检测2 2n-1n-1

8、 1(mod n)1(mod n)。是，输出。是，输出“素数素数”；否则输出；否则输出“合数合数”。2021-9-2221 of 158算法算法Ptest1(n)Ptest1(n)输入：奇整数输入：奇整数n,n5n,n5输出：输出： “ “prime” prime” 或者或者 “ “composite” composite” 1. if ExpMod(2,n-1,n) =1 then return prime1. if ExpMod(2,n-1,n) =1 then return prime2. else return composite 2. else return composite 算法

9、算法Ptest1Ptest1只对只对a=2a=2进行测试进行测试, ,如果如果n n为合数且为合数且Ptest1Ptest1输出为输出为“素数素数”，则称，则称n n为基为基2 2伪素数。伪素数。 341341满足上述条件，但是满足上述条件，但是341341是合数是合数. .2021-9-2222 of 158改进方法是随机选取改进方法是随机选取2-n-22-n-2中的数做为中的数做为a a，再进行测试，再进行测试. . 取取a=3a=3，3 3340340(mod 341)(mod 341) 5656，341341不是素数不是素数. . 算法算法Ptest2(n)Ptest2(n) 1. a

10、 1. aRandom(2,n-2)Random(2,n-2) 2. if Expmod(a,n-1,n)=1 then return prime 2. if Expmod(a,n-1,n)=1 then return prime 3. else return composite 3. else return composite2021-9-2223 of 158对所有与对所有与n n互素的正整数互素的正整数a a，都满足上述条件的，都满足上述条件的合数合数n n称为称为Carmichael Carmichael 数，如数，如561561，11051105，17291729，24652465等

11、。等。CarmichaelCarmichael数非常少，小于数非常少，小于10108 8的只有的只有255255个。个。 如果如果n n为合数，但不是为合数，但不是CarmichaelCarmichael数，算法数，算法Ptest2 Ptest2 测试测试n n为合数的概率至少为为合数的概率至少为1/2. 1/2. 但是这但是这个算法不能解决个算法不能解决 CarmichaelCarmichael数的问题。数的问题。2021-9-2224 of 158定理定理2 2 如果如果n n为素数，则方程为素数，则方程x x2 2 1(mod n)1(mod n)的的根只有两个，即根只有两个，即x=1x

12、=1，x=-1x=-1（或（或x=n-1x=n-1）。）。证明证明 x x2 2(mod n)(mod n) 1 1 x x2 2-1-1 0(modn)0(modn) (x+1)(x-1) (x+1)(x-1) 0(modn)0(modn) x+1 x+1 0 0或或 x-1x-1 0 0 x=n-1 x=n-1或或 x=x=1 12021-9-2225 of 158称称x x1 1的根为非平凡的。根据定理的根为非平凡的。根据定理2 2，如果方程，如果方程有非平凡的根，则有非平凡的根，则n n为合数。例如为合数。例如: : x x2 2(mod 5)(mod 5) 1 1 x=1 x=1或或

13、x=4x=4 x x2 2(mod 12)(mod 12) 1 1 x=1 x=1 或或x=11x=11或或x=5x=5或或x=7x=75 5和和7 7是非平凡的根。是非平凡的根。设设n n为素数，存在为素数，存在q,mq,m使得使得n-1=2n-1=2q qm, (qm, (q 1)1)。序列。序列 )(mod),.,(mod),(mod),(mod242nanananammmmq的最后一项为的最后一项为a an-1n-1(mod n), (mod n), 而且每一项是前面一项的而且每一项是前面一项的平方。对于任意平方。对于任意k k（k=0,1,k=0,1,q-1q-1）, , 判断判断)(mod2namk是否为是否为1 1和和n-1n-12021-9-2226 of 158Instant Insanity游戏游戏 针对的是四个立方体。立方体针对的是四个立方体。立方体六个面中的每一个都涂有红六个面中的每一个都涂有红(R)(