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