《算法设计与分析》-第七章-随机算法及计算复杂性概要课件.ppt
第七章第七章 随机算法及随机算法及NP完全问题完全问题 l7.1 随机算法引言l7.2 随机算法的类型l7.3 随机数发生器l7.4 数值概率算法l7.5 舍伍德(Sherwood)算法l7.6 拉斯维加斯（Las Vegas）算法l7.7 蒙特卡罗（Monte Carlo）算法l7.8 NP完全问题7.1 随机算法引言随机算法引言l确定性的算法：算法的每一个计算步骤都是确定的，对于相同的输出，每一次执行过程都会产生相同的输出。l随机算法：非形式描述随机算法为使用随机函数产生器的算法。算法中的一些判定依赖于随机函数产生器的输出。随机算法对于相同的输入，在不同的运行过程中会得到不同的输出。对于相同的输入，随机算法的执行时间也可能随不同的运行过程而不同。8.1 随机算法引言随机算法引言l随机算法的优点：1、执行时间和空间，小于同一问题的已知最好的确定性算法；2、实现比较简单，容易理解。l很多确定性的算法，其性能很坏。可用随机选择的方法来改善算法的性能。l某些方面可能不正确，对特定的输入，算法的每一次运行不一定得到相同结果。出现这种不正确的可能性很小，以致可以安全地不予理睬。7.2 随机算法的类型随机算法的类型 l数值概率算法l拉斯维加斯（Las Vegas）算法l蒙特卡罗（Monte Carlo）算法l舍伍德（Sherwood）算法。7.2 随机算法的类型随机算法的类型l1、数值概率算法：用于数值问题的求解。所得到的解几乎都是近似解，近似解的精度随着计算时间的增加而不断地提高。l2、舍伍德（Sherwood）算法：很多具有很好的平均运行时间的确定性算法，在最坏的情况下性能很坏。引入随机性加以改造，可以消除或减少一般情况和最坏情况的差别。7.2 随机算法的类型随机算法的类型l3、拉斯维加斯（Las Vegas）算法：要么给出问题的正确答案，要么得不到答案。反复求解多次，可使失效的概率任意小。l4、蒙特卡罗（Monte Carlo）算法：总能得到问题的答案，偶然产生不正确的答案。重复运行，每一次都进行随机选择，可使不正确答案的概率变得任意小。7.3 随机数发生器随机数发生器 l产生随机数的公式：产生065535的随机数 序列，b、c、d为正整数，称为所产生的随机序列的种子。常数b、c，对所产生的随机序列的随机性能有很大的关系，b通常取一素数。7.3 随机数发生器随机数发生器l#defineMULTIPLIER0 x015A4E35L;l#defineINCREMENT1;lstatic unsigned long seed;lvoid random_seed(unsigned long d)llif(d=0)l seed=time(0);lelsel seed=d;llunsigned int random(unsigned long low,unsigned long high)llseed=MULTIPLIER*seed+INCREMENT;lreturn(seed 16)%(high low)+low);l7.4 数值概率算法数值概率算法l l例：用随机投点法计算例：用随机投点法计算 值值l设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为 。所以当n足够大时，k与n之比就逼近这一概率。从而7.4 数值概率算法数值概率算法lpublic double darts(int n)l /用随机投点法计算值l int k=0;l for(int i=1;i=n;i+)l double x=dart.fRandom();l double y=dart.fRandom();l if(x*x+y*y)=1)k+;l l return 4*k/(double)n;l 7.5 舍伍德舍伍德(Sherwood)算法算法一、确定性算法的平均运行时间lTA(x)：确定性算法对输入实例的运行时间。lXn：规模为的所有输入实例全体。l算法的平均运行时间：l存在实例 ，。l例：快速排序算法l当输入数据均匀分布时，运行时间是 。l当输入数据按递增或递减顺序排列时，算法的运行时间变坏7.5 舍伍德舍伍德(Sherwood)算法算法二、舍伍德算法的基本思想消除不同输入实例对算法性能的影响，使随机算法对规模为的每一个实例，都有：三、期望运行时间：l 当s(n)与 相比很小可以忽略时，舍伍德算法有很好的性能。l对所有输入实例而言，运行时间相对均匀。时间复杂性与确定性算法的时间复杂性相当.7.5 舍伍德舍伍德(Sherwood)算法算法l随机快速排序算法 l算法算法9.1 随机选择枢点的快速排序算法l输入：输入：数组A,数组元素的的起始位置low,终止位置highl输出：输出：按非降顺序排序的数组Al 1.template l2.void quicksort_random(Type A,int low,int high)l3.l 4.random_seed(0);/*选择系统当前时间作为随机数种子*/l 5.r_quicksort(A,low,high);/*递归调用随机快速排序算法*/l 6.7.5 舍伍德舍伍德(Sherwood)算法算法l1.void r_quicksort(Type A,int low,int high)l2.l 3.int k;l 4.if(low0，使得对的所有实例p，都有p(x)=，则失败的概率小于1-。l连续运行k次，失败的概率降低为(1-)k。lk充分大，(1-)k趋于0。7.6 拉斯维加斯（拉斯维加斯（Las Vegas）算法）算法l例：识别重复元素l考虑一个有n个数字的数组a，其中有n/2个不同的元素，其余元素是另一个元素的拷贝，即数组中共有（n/2）+1个不同的元素。问题是要识别重复的元素。l确定性算法：至少需要（n/2）+2个时间步。7.6 拉斯维加斯（拉斯维加斯（Las Vegas）算法）算法l拉斯维加斯（Las Vegas）算法int RepeatedElement(Type a,int n)while(1)int i=random()%n+1;int j=random()%n+1;if(i!=j)&(ai=aj)return(i);7.6 拉斯维加斯（拉斯维加斯（Las Vegas）算法）算法lwhile循环则任何一次迭代中退出的概率为p=.当n 10时，p 1/5,则不退出的 概率 4/5。l算法在前calogn(c为固定常数)次迭代内不退出的概率(4/5)calogn=n-calog(4/5),若取c 1/log(5/4),则其值 n-a,l因此，算法在calogn次迭代以内终止的概率 1-n-a。每次迭代花费O(1)的时间，算法的执行时间为O(logn)。7.7 蒙特卡罗（蒙特卡罗（Monte Carlo）算法）算法 l蒙特卡罗算法则在一般情况下可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确。l设p是一个实数，且1/2p1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称p-1/2是该算法的优势。l如果对于同一实例，蒙特卡罗算法不会给出2个不同的正确解答，则称该蒙特卡罗算法是一致的。7.7 蒙特卡罗（蒙特卡罗（Monte Carlo）算法）算法l数组的主元素问题 一、问题ln个元素的数组A，A中元素x，若A中一半以上元素与x相同，称x是A的主元素。l例：序列1,3,2,3,3,4,3中，元素3是主元素。二、一般方法l每个元素和其它元素比较，并计数。如果计数值大于n/2，该元素就是的主元素。l元素比较次数为 。7.7 蒙特卡罗（蒙特卡罗（Monte Carlo）算法）算法l三、蒙特卡罗算法l1、随机选择元素Ai进行测试，若返回true，Ai就是主元素；否则不是主元素。7.7 蒙特卡罗（蒙特卡罗（Monte Carlo）算法）算法l算法算法9.7 求数组A的主元素l输入：输入：n个元素的数组Al输出：输出：数组A的主元素 BOOL majority(Type A,Type&x,int n)int i,j,k;random_seed(0);i=random(0,n-1);k=0;for(j=0;jn/2)x=Ai;return TRUE;else return FALSE;7.7 蒙特卡罗（蒙特卡罗（Monte Carlo）算法）算法l2、如果存在主元素，以大于1/2的概率返回true，小于1/2的概率返回false。l连续运行k次，返回的概率减少为2-k，算法错误的概率为2-k。l希望错误概率小于，则令：2-k=l k=log(1/)l算法修改为：7.7 蒙特卡罗（蒙特卡罗（Monte Carlo）算法）算法lBOOL majority_monte(Type A,Type&x,int n,double e)l int t,s,i,j,k;BOOL flag=FALSE;l random_seed(0);s=log(1/e);l for(t=1;t=s;t+)l i=random(0,n-1);k=0;l for(j=0;jn/2)x=Ai;flag=TRUE;break;l l return flag;l l算法的错误概率小于所给参数e。算法的运行时间为O(nlog(1/e)。7.7 蒙特卡罗（蒙特卡罗（Monte Carlo）算法）算法l素数测试 一、一般方法被测试的数除以2到 的数，余数为0，是合数，否则是素数。二、二、蒙特卡罗算法 素数测试WilsonWilson定理定理定理定理：对于给定的正整数n，判定n是一个素数的充要条件是(n-1)!-1(mod n)。费尔马小定理费尔马小定理费尔马小定理费尔马小定理：如果p是一个素数，且0ap，则ap-1(mod p)。二次探测定理二次探测定理二次探测定理二次探测定理：如果p是一个素数，且0 xp，则方程x21(mod p)的解为x=1，p-1。int power(int a,int p,int n)/计算 ap mod n，并实施对n的二次探测 int x,result;if(p=0)result=1;else x=power(a,p/2,n);/递归计算 result=(x*x)%n;/二次探测 if(result=1)&(x!=1)&(x!=n-1)composite=true;if(p%2)=1)/p是奇数 result=(result*a)%n;return result;boolean prime(int n)/素数测试的蒙特卡罗算法 rnd=new Random();int a,result;composite=false;a=rnd.random(n-3)+2;result=power(a,n-1,n);if(composite|(result!=1)return false;else return true;算法prime是一个偏假3/4正确的蒙特卡罗算法。通过多次重复调用错误概率不超过(1/4)k。这是一个很保守的估计，实际使用的效果要好得多。7.8 NP难与难与NP完全问题完全问题l一、易解的问题和难解的问题l存在多项式时间算法的问题，称为易解的问题l指数时间算法或排列时间算法的问题，称为难解的问题l二、难解问题的计算相关性l计算相关：某类问题可以归约为另一类问题l计算相关的问题，若它们之一可用多项式时间求解，则其它同类问题也可用多项式时间求解；若它们之一肯定不存在多项式时间算法，则同类的其它问题，也肯定不会找到多项式时间算法。7.8 NP难与难与NP完全问题完全问题P类和类和NP类问题类问题 l定义定义12.1 是问题的一个算法。如果在处理问题的实例时，在算法的整个执行过程中，每一步只有一个确定的选择，就说算法是确定性的算法。l定义定义12.2 如果对某个判定问题，存在着一个非负整数k，对输入规模为n的实例，能够以O(nk)的时间运行一个确定性的算法，得到yes或no的答案，则该判定问题是一个p类判定问题。7.8 NP难与难与NP完全问题完全问题 P类和类和NP类问题类问题 l定义定义12.5 如果对某个判定问题，存在着一个非负整数k，对输入规模为n的实例，能够以O(nk)的时间运行一个非确定性的算法，得到yes或no的答案，则该判定问题是一个NP类判定问题。l特性：存在确定性的算法，能够以多项式时间，来检查和验证在推测阶段产生的答案。7.8 NP难与难与NP完全问题完全问题NP难问题难问题lNP难l定义定义12.6 令是一个判定问题，如果对NP中的每一个问题 NP，有 ，就说判定问题是一个NP难题。7.8 NP难与难与NP完全问题完全问题NP完全问题完全问题lNP完全问题 l定义定义12.7 令是一个判定问题，如果：l(1)NP，并且：l(2)对NP中的所有问题 NP，都有 ；则称判定问题是NP完全的。7.8 NP难与难与NP完全问题完全问题lNP难题和NP完全问题的差别l是NP完全问题，是NP难题，l则必定在NP类中，而不一定在NP类中。7.8 NP难与难与NP完全问题完全问题l1、归约的传递性 l定理定理12.3 令 、和 是三个判定问题，满足 ，及 ，则有 。7.8 NP难与难与NP完全问题完全问题lNP完全问题的特性 l定理定理12.4 令 和 是NP中的两个问题，使得 。如果 是NP完全的，则 也是NP完全的。7.8 NP难与难与NP完全问题完全问题lNP完全问题的证明：l证明下面两件事情：l(1)，并且：l(2)存在一个NP完全问题 ，使得 ；7.8 NP难与难与NP完全问题完全问题l定理定理12.5（Cook定理）可满足性问题SATISFIABILITY是NP完全的。lCook定理的意义：lCook定理给出了第一个NP完全问题，使得对任何问题，只要能够证明 ，并且SATISFIABILITY ，那么 ，就是NP完全的 7.8 NP难与难与NP完全问题完全问题l部分的NP完全问题树 7.8 NP难与难与NP完全问题完全问题l通常认为的P、NP、NP Complete、NP Hard问题的关系：PNPNP CompleteNP Hard7.8 NP难与难与NP完全问题完全问题lNP完全问题的特性为：当且仅当所有其它NP完全问题可以在多项式时间内求解，该问题可以在多项式时间内求解。l如果一个NP难问题可以在多项式时间内求解，则所有的NP完全问题都可以在多项式时间内求解。lNP完全和NP难问题都不是多项式时间可解的。
