算法设计与分析第7章概率

1、2022-2-26计算机算法设计与分析1第七章随机化(概率)算法2022年2月26日2随机化算法的基本思想n是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法。n随机化算法把“对于所有合理的输入都必须给出正确的输出”这一求解问题的条件放宽，把随机性随机性的选择注入到算法中，在算法执行某些步骤时，可以随机地选择下一步该如何进行，同时允许结果以较小的概率出现错误允许结果以较小的概率出现错误，并以此为代价，获得算法运行时间的大幅度减少。2022年2月26日3随机化算法的基本概念例如，判断表达式f(x1, x2, , xn)是否恒等于0。随机化算法首先生成一个随机n元向量(r1,

2、 r2, , rn)，并计算f(r1, r2, , rn)的值，如果f(r1, r2, , rn)0，则f(x1, x2, , xn)0；如果f(r1, r2, , rn)0，则或者f(x1, x2, , xn)恒等于0，或者是(r1, r2, , rn)比较特殊，如果这样重复几次，继续得到f(r1, r2, , rn)0的结果，那么就可以得出f(x1, x2, , xn)恒等于0的结论，并且测试的随机向量越多，这个结果出错的可能性就越小。2022年2月26日4随机化算法的基本特征 一般情况下，随机化算法具有以下基本特征：（1）算法的输入包括两部分，一部分是原问题的输入，另一部分是一个供算法进

3、行随机选择的随机数序列；（2）算法在运行过程中，包括一处或若干处随机选择，根据随机值来决定算法的运行；（3）算法的结果不能保证一定是正确的，但可以限定其出错概率；（4）算法在不同的运行中，对于相同的输入实例可以有不同的结果，因此，对于相同的输入实例，概率算法的执行时间可能不同。2022年2月26日5随机化算法的随机性n对于同一实例的多次执行, 效果可能完全不同；n时间复杂性的一个随机变量；n解的正确性和准确性也是随机的。2022年2月26日6随机化算法的分类n数值随机化算法数值随机化算法主要用于数值问题求解算法的输出往往是近似解近似解的精确度与算法执行时间成正比n蒙特卡罗算法蒙特卡罗算法主要用

4、于求解需要准确解的问题算法可能给出错误解获得精确解概率与算法执行时间成正比2022年2月26日7概率算法的分类n拉斯维加斯算法拉斯维加斯算法一旦找到一个解, 该解一定是正确的找到解的概率与算法执行时间成正比增加对问题反复求解次数, 可使求解无效的概率任意小n舍伍德算法舍伍德算法一定能够求得一个正确解确定算法的最坏与平均复杂性差别大时, 加入随机性, 即得到Sherwood算法消除最坏行为与特定实例的联系2022年2月26日8随机化算法的性能分析n随机化算法分析的特征随机化算法分析的特征每次运行实例仅依赖于随机选择, 不依赖于输入的分布确定算法的平均复杂性分析: 依赖于输入的分布对于每个输入都要

5、考虑算法的概率统计性能n随机化算法分析的目标随机化算法分析的目标平均时间复杂性: 时间复杂性随机变量的均值获得正确解的概率获得优化解的概率解的精确度估计2022-2-26计算机算法设计与分析9随机数的产生n在概率算法中随机数的产生是个非常重要的部分，但在计算机上无法产生真正的随机数。n任何一种随机数的产生都和给定的初始条件有关，当初始条件相同时，会给出同样的随机数序列。还有，该随机数序列存在周期，即经过一个周期后，序列会重复出现。称为伪随机数。 2022-2-26计算机算法设计与分析10线形同余算法n最简单的伪随机数是用线性同余算法产生的。公式如下： na0=dan=(b*an-1+c) mo

6、d m ，n=1,2,n 其中，d被称为种子。b,d,c,m均大于0。而且这几个数直接关系到随机序列的性能。n 线性同余算法实现简单，速度快，具有较好的统计性能，广泛应用于仿真，但不能用于加密。大多数系统中提供的random函数都是采用此方法实现。2022-2-26计算机算法设计与分析11线性反馈移位寄存器(LFSR) n线性反馈移位寄存器(LFSR)是一个反馈移位寄存器。其反馈函数是寄存器中某些位的简单异或，这些位也称之为抽头序列。n一个n位的LFSR能够在重复之前产生2n-1 位长的伪随机序列。只有具有一定抽头序列的LFSR才能通过所有2n-1个内部状态，产生2n-1 位长的伪随机序列，这

7、个输出的序列就称之为m序列。2022-2-26计算机算法设计与分析12用随机投点法计算值n向正方形随机投掷n个点, 设落入其内切圆的点数为k。n由于是均匀分布, 因此落入圆内的概率为 4242rrn当n足够大时，k 与 n 之比就逼近于这一概率，从而nk42022-2-26计算机算法设计与分析13计算的算法ndouble PI (int n) double x, y; int k = 0; for (int i=1; i=n; i+) x=Random(); /*随机产生一个(0,1)区间的数*/ y=Random(); if (x*x+y*y=1) k+; return k/double(n

8、); 2022-2-26计算机算法设计与分析14用随机投点法计算定积分n设f(x)是0, 1上的连续函数，且0f(x)1，计算积分y = f(x)Gn在正方形中随机点落在曲线 y = f(x)下面的概率为10dx)x(fIn假设向单位正方形内随机投入n个点(xi, yi)，若有m个点落入G中，由概率论可知，如果这些点在正方形内均匀分布，则Im/n。n当n足够大时，统计出m的值，就可以近似地求出I的值。IdxxfdydxPxf 1010)(0)(2022-2-26计算机算法设计与分析15计算连续函数的算法ndouble Darts (int n) double x, y; int k = 0;

9、for (int i=1; i=n; i+) x=Random(); /*随机产生一个(0,1)区间的数*/ y=Random(); if (y=f(x) k+; return k/double(n); 2022-2-26计算机算法设计与分析16随机抽样 n在n个元素的集合中随机抽取m(0mn)个无重复的元素。 2022-2-26计算机算法设计与分析17随机抽样n我们采用下面的方法进行选择： 1、首先将n个元素都标记为“未选择”； 2、重复下列步骤直到抽取了m个不同的元素 产生一个1至n间的随机数r； 如果r标记为“未选择”，将它标记为“已选择”，并加入到抽样中。 2022-2-26计算机算法

10、设计与分析18随机抽样算法nint RandomSampling(Sn, Am, m) n/* 本函数在有n个元素的数组S中随机抽取m个不同的元素存放到数组A中 */n mark1.n = False; count=0;n while(count =n/2时，选择n-m个元素，抛弃掉它们并将剩余元素作为抽样。 2022-2-26计算机算法设计与分析20舍伍德算法 n舍伍德算法总能求得问题的一个解，且所求得解的结果总是正确的。其主要目的是消除算法所需计算时间对输入实例的依赖。n当一个确定型算法最坏情况下的计算复杂性与其平均情形下的复杂度有较大差别时，可以在这个确定型算法中引入随机性将它改造成一个

11、舍伍德算法，消除或减少问题的好坏实例间的这种差别。n舍伍德算法的精髓不是避免算法的最坏情况行为，而是设法消除这种最坏情形行为与特定实例之间的关联性。 2022-2-26计算机算法设计与分析21舍伍德算法与快速排序n舍伍德算法的一个典型应用就是在快速排序中。 n在快速排序算法中，若用拟中位数作为划分标准，可保证在线性时间内完成。但是确定拟中位数要付出额外开销。若选用第一个元素为划分基准，最坏时的时间复杂性为O(n2)。n为了改进它的性能，我们可以改变基准选取的原则，不是每次都选取待排序列的第一个元素，而是在待排序列中随机选取一个元素作为基准(每次将选择到的元素与第一个元素交换，然后就和确定性算法

12、一样做)。既保证算法的线性时间平均性能，又避免了计算拟中位数的麻烦。2022-2-26计算机算法设计与分析22int qkpass(int r, int low, int high); int temp; temp=rlow; /*以第一个元素为基准值，并把这个位置腾出来以第一个元素为基准值，并把这个位置腾出来*/ while (low high ) while (low high & rhightemp) high=high-1; rlow=rhigh; /* 找到一个比基准小的元素并把它放到空当找到一个比基准小的元素并把它放到空当*/ /*现在的空当在现在的空当在high处，如果不

13、存在这样的元素，处，如果不存在这样的元素，low=high*/ while (low high & rlowtemp) low=low+1; rhigh=rlow; /*找到一个比基准大的元素并把它放到空当找到一个比基准大的元素并把它放到空当*/ /*现在的空当重新回到现在的空当重新回到low处，如果不存在这样的元素，处，如果不存在这样的元素，low=high*/ rlow=temp; return(low) 2022-2-26计算机算法设计与分析23线性时间选择算法n在无序序列中选择第K大（或小）的元素是最常见的问题。若K=1或K=n，则显然可以在O(n)的时间内解决；但若K=(n+

14、1)/2，就要难得多了。n借用快速排序来解决。算法的基本思路也是采用划分，以基准元素为标准，将序列划分成大于和小于基准的两部分，第K大元素或者就是基准，否则只可能位于其中的一部分，再对这一部分进行递归处理就可以了。为了避免在最坏情形下时间复杂度达到O(n2)，这里对基准的选取需要加入随机性。2022-2-26计算机算法设计与分析24选取第k大的元素int randomSelect(int r, int low, int high, int k) /在区间rlow.high中选取第k大的元素,k1.n if (lowhigh) return rlow; p=randomPartition(r,l

15、ow,high); /对r进行划分,返回基准位置p if(kp) return rp; /基准恰好就是第k个元素 if (kp) return randomSelect(r,low,p-1,k); else return randomSelect(r,p+1,high,k);2022-2-26计算机算法设计与分析25定位基准元素 int randomPartition(int r,int low, int high ) /* 找rlow.high中的基准，并使得基准前面的元素均小于基准值，后面的元素均大于等于基准值，最终返回基准所在的位置 */ i=random(low,high); /产生一

16、个low.high之间的随机数 temp=ri; /以第i个元素为基准 ri=rlow; /把第一个位置腾出来 while (low high) while (low high & rhightemp) high-; rlow=rhigh; /找到一个比基准小的元素放到空当，新的空当在high处 while (low high & rlowtemp) low+; rhigh=rlow; /找到一个比基准大的元素放到空当，空当重新回到low处 rlow=temp; return low; /返回基准的位置 2022-2-26计算机算法设计与分析26“洗牌”算法n有时候会遇到这样的

17、情况，即所给定的确定型算法无法直接修改成舍伍德算法。此时可以借助随机预处理技术，不改变原有的确定型算法，仅对其输入进行随机洗牌，同样可以收到舍伍德算法的效果。n所谓随机洗牌就是将输入的数组随机排列。下面就是一个随机洗牌算法。 nvoid shuffle(int a, int n) /将数组a中的元素进行随机排列 for(i=0;in/2;i+) rnd=random(n-i)+i; swap(a,rnd,i); 2022-2-26计算机算法设计与分析27拉斯维加斯算法（ Las Vegas ） n舍伍德算法：计算时间复杂性对所有实例而言相对均匀；但与其相对应的确定性算法相比，其平均时间复杂性没

18、有改进。n拉斯维加斯算法：显著地改进算法的有效性，甚至对某些迄今为止找不到有效算法的问题，也能找到满意的算法；但它所做的随机性决策有可能导致算法找不到需要的解。n由于后者的原因，通常用boolean型方法表示拉斯维加斯型算法。2022-2-26计算机算法设计与分析28倔强算法n拉斯维加斯算法的典型调用形式为boolean success = LV(x, y)；其中x是输入参数，当success的值为true时，y返回问题的解，当success的值为false时，y算法未能找到问题的一个解。此时可对同一实例再次独立地调用相同的算法。n由于拉斯维加斯算法所做的随机决策有可能导致找不到所需要的解，就

19、用下面的倔强算法来求解。 pubic static void obstinate(Object x, Object y) /*反复调用拉斯维加斯算法LV(x, y)，直到找到问题 的一个解y*/ boolean success = false; while (!success) success = LV(x, y); 2022-2-26计算机算法设计与分析29Las Vegas算法求解n后问题nLas Vegas算法的特点是随机性地进行决策。n对n后问题，Las Vegas算法是随机地产生一组王后放置的位置。若成功了，便找到了一个解；若失败了，就整个重来，再随机产生另外一组王后的位置。这样作，

20、直至找到解。n此算法采用了与前面回溯法完全不同的策略，一旦有一列中的皇后没有位置可放，需要全部重新开始。 2022-2-26计算机算法设计与分析30n 后问题n问题描述：等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。n解的表示： 用 n 元组 rec1:n 表示皇后i放在第i行的第reci列。n约束条件： 不在同一列：reci互不相同，即recirecj，当ij。 不在同一行：皇后i一定放在第i行，表示法的约定。 不在同一斜线：|reci-recj|i-j|。2022-2-26计算机算法设计与分析31QueensLV算法int queensLV(int re

21、c)int k,i=1,found=1; /第i个皇后放在第k列 while(i=N & found) found=0; for(k=1;k=N & !found; k+) /准备在当前这一行放置皇后 reci=k; if(place(rec,i) /判断该位置能否放置皇后 if(rand()%2=0) found=1; /即便能放，也还要进行随机处理，只有50%的机会 if (found) i+; /放下一行 return found; /如果found=1，表示找到一种方案 2022-2-26计算机算法设计与分析32nint place(int rec, int i) in

22、t j; for(j=1;ji;j+) if(abs(i-j)=abs(reci-recj) | recj=reci ) return 0; return 1; nvoid nQueen(int N) /解n后问题的拉斯维加斯算法 int recN+1 ; for (int i = 1; i= N; i+) reci = 0; /反复调用随机放置n个皇后的拉斯维加斯算法，直至放置成功 while (!queensLV(N); 2022-2-26计算机算法设计与分析33 n上述算法每次都重新开始，似乎过于悲观。如果将上述随机放置策略与回溯法相结合，可能会获得更好的效果。n可以先在棋盘的前面若干行

23、随机地放置皇后，然后在后继行中用回溯法继续放置，直到找到一个解或宣告失败。随机放置的皇后越多，后继回溯所需的时间就越少，但失败的概率也就越大。QueensLV算法的改进2022-2-26计算机算法设计与分析34蒙特卡罗算法n蒙特卡罗算法用于求解问题的准确解。n对于一些问题来说，近似解毫无意义。例如判定问题，只要回答“是”或“否”，不存在近似解回答。又如，要求一个整数的因子时所给出的解答必须是准确的，一个整数的近似因子是没有任何意义的。n蒙特卡罗算法能求得一个解，但未必是正确的。其求得正确解的概率依赖于算法所用的时间。所用时间越多，得到正确解的概率就越高，但它的缺点也在于此。在一般情况下，无法有

24、效地判定所得到的解是否肯定正确。 2022-2-26计算机算法设计与分析35蒙特卡罗算法的基本思想n设p是一个实数，且1/2p1。若一个蒙特卡罗算法对于问题的任意实例得到正确解的概率不小于p，则称该蒙特卡罗算法是蒙特卡罗算法是p正确的正确的。且称p-1/2是该算法的优势。n若对于同一实例，蒙特卡罗算法不会给出两个不同的正确解答，则称该蒙特卡罗算法是一致蒙特卡罗算法是一致的的。n对于一个一致的p正确蒙特卡罗算法，要提高获得正确解的概率，只要执行该算法若干次，并选择出现频率次数最高的解即可。2022-2-26计算机算法设计与分析36关于正确解的概率n在一般情况下，设和是两个正实数，且+0.5，可以

25、放松到p0。2022-2-26计算机算法设计与分析38主元素问题 n设T0.n-1是一个有n个元素的数组。当|i|Ti=x|n/2时，称元素x是数组T的主元素。我们用下面的方法来判断T中是否含有主元素：nbool majority(int T, int n) x=Trandom()%n; /随机选择一个元素看成是主元素 count=0; for(i=0;in/2); /当countn/2时，T含有主元素，返回Ture 2022-2-26计算机算法设计与分析39对majority算法的分析n若算法返回结果为true，即随机选择的元素x是数组T的主元素，则显然数组T含有主元素。反之, 若返回结果为

26、false, 则数组T未必没有主元素。由于若数组T有主元素，则它的非主元素个数小于n/2, 故上述情况发生的概率小于1/2。由此可见， majority算法是一个偏真的1/2正确算法。n或换句话说，若数组T含有主元素,则算法以大于1/2的概率返回true； 若数组T没有主元素，则算法肯定返回false。2022-2-26计算机算法设计与分析40重复2次调用的majority2算法n在实际使用时，50%的错误概率是不可容忍的。重复调用技术可将错误降低到任何可接受值的范围。现在讨论重复调用2次的算法majority2。nbool majority2(int T, int n) if(majorit

27、y(T,n) return true; else return majority(T,n); 2022-2-26计算机算法设计与分析41对majority2算法的分析n若数组T不含主元素，则每次调用majority(T, n)返回false, 从而majority2肯定也是返回false。若数组T含有主元素, 则算法majority(T, n)返回true的概率是p1/2，而当majority(T, n)返回true时, majority2也返回true。n另一方面,majority2第一次调用majority(T, n)返回false的概率为1-p, 第二次调用majority(T, n)仍

28、以概率p返回true。因此当数组T含有主元素时, majority2返回true的概率是p+(1-p)p=1-(1-p)23/4。即算法majority2是一个偏真3/4正确的MC蒙特卡罗算法。2022-2-26计算机算法设计与分析42错误概率小于的偏真算法n由于重复调用majority所得到的结果是相互独立的，若T确实含有主元素，则k次重复调用majority仍然得到false的概率小于2-k。另一方面，只要有一次调用返回值为true，即可断定T中含有主元素。n对于任何给定的0，下面算法majorityMC重复调用log(1/)次算法majority。它是一个偏真的蒙特卡罗算法，且错误概率小于。nbool majorityMC(int T, int n, double e) int i, k=log(1/)/log2.0; for(i=0; i 1) n if (power % 2 = = 1) /若power是奇数n other *= a; other %= n;n power