算法设计与分析第七章随机算法及计算复杂性ppt课件.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算法的每一个计算步骤都是确定的，l对于一样的输出，每一次执行过程都会产生一样的输出l随机算法：非方式描画l随机算法为运用随机函数产生器的算法算法中的一些断定依赖于随机函数产生器的输出l随机算法对于一样的输入，在不同的运转过程中会得到不同的输出l对于一样的输入，随机算法的执行时间也能够随不同的运转过程而不同8.1 随机算法引言随机算法引言l随机算法的优点：l1、执行时间和空间，小于同一问题的知最好确实定性算法；l2、实现比较简单，容易了解 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产生随机数的公式：ll 产生0~65535的随机数 序列，l b、c、d为正整数，称为所产生的随机序列的种子l 常数b、c，对所产生的随机序列的随机性能有很大的关系，b通常取一素数 7.3 随机数发生器随机数发生器l#defineMULTIPLIER0x015A4E35L;l#defineINCREMENT1;lstatic unsigned long seed;lvoid random_seed(unsigned long d)l{lif (d==0)l seed = time(0);lelsel seed = d;l}lunsigned int random(unsigned long low,unsigned long high)l{lseed = MULTIPLIER * seed + INCREMENT;lreturn ((seed >> 16) % (high – low) + low);l}7.4 数值概率算法数值概率算法l l例：用随机投点法计算例：用随机投点法计算值值l l设有一半径为设有一半径为r r的圆及其外切四边形。

向该正的圆及其外切四边形向该正方形随机地投掷方形随机地投掷n n个点设落入圆内的点数为个点设落入圆内的点数为k k由于所投入的点在正方形上均匀分布，因此所由于所投入的点在正方形上均匀分布，因此所投入的点落入圆内的概率为投入的点落入圆内的概率为 所以当n n足够大时，足够大时，k k与与n 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)算法算法一、确定性算法的平均运转时间TA(x) ：确定性算法对输入实例的运转时间。

Xn ：规模为的一切输入实例全体算法的平均运转时间：存在实例 ， 例：快速排序算法当输入数据均匀分布时，运转时间是 当输入数据按递增或递减顺序陈列时，算法的运转时间变坏7.5 舍伍德舍伍德(Sherwood)算法算法二、舍伍德算法的根本思想消除不同输入实例对算法性能的影响，使随机算法对规模为的每一个实例，都有：三、期望运转时间： 当s(n)与 相比很小可以忽略时，舍伍德算法有很好的性能对一切输入实例而言，运转时间相对均匀时间复杂性与确定性算法的时间复杂性相当 .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 (low

7.6 拉斯维加斯〔拉斯维加斯〔Las Vegas〕算法〕算法 一、普通概念拉斯维加斯算法有时运转胜利，有时失败，需求反复运转同一实例，直到胜利为止BOOL las_vegas()：解问题的某个实例的代码段运转胜利前往true，否那么前往false拉斯维加斯算法反复地运转下面的代码段：while(!las_vegas(P(x))) ;直到运转胜利前往为止7.6 拉斯维加斯〔拉斯维加斯〔Las Vegas〕算法〕算法lp(x)：对输入实例胜利地运转las_vegas的概率l假设存在常数δ>0，使得对的一切实例p，都有p(x)>= δ ，那么失败的概率小于1- δ l延续运转k次，失败的概率降低为(1- δ )klk充分大， (1- δ )k趋于07.6 拉斯维加斯〔拉斯维加斯〔Las Vegas〕算法〕算法l例：识别反复元素l思索一个有n个数字的数组a[]，其中有n/2个不同的元素，其他元素是另一个元素的拷贝，即数组中共有〔n/2〕+1个不同的元素问题是要识别反复的元素l确定性算法：l至少需求〔n/2〕+2个时间步7.6 拉斯维加斯〔拉斯维加斯〔Las Vegas〕算法〕算法l拉斯维加斯〔Las Vegas〕算法lint RepeatedElement(Type a[],int n){lwhile (1){lint i=random()%n+1;lint j= random()%n+1;lif((i!=j)&&(a[i]==a[j])) return(i);l}l}7.6 拉斯维加斯〔拉斯维加斯〔Las Vegas〕算法〕算法lwhile循环那么任何一次迭代中退出的概率为p= .当n ≥ 10时， p ≥ 1/5,那么不退出的l 概率≤ 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/2

l元素比较次数为 7.7 蒙特卡罗〔蒙特卡罗〔Monte Carlo〕算法〕算法l三、蒙特卡罗算法l1、随机选择元素A[i]进展测试，假设前往true， A[i]就是主元素；否那么不是主元素7.7 蒙特卡罗〔蒙特卡罗〔Monte Carlo〕算法〕算法l算法算法9.7 求数组求数组A的主元素的主元素l输入：输入：n个元素的数组个元素的数组A[]l输出：数组输出：数组A的主元素的主元素l BOOL majority(Type A[],Type &x,int n) {l int i,j,k;lrandom_seed(0);l i = random(0,n-1) ; k = 0;lfor (j=0;jn/2) {x = A[i]; return TRUE;}l else return FALSE;l}7.7 蒙特卡罗〔蒙特卡罗〔Monte Carlo〕算法〕算法l2、假设存在主元素，以大于1/2的概率前往true，小于1/2的概率前往falsel延续运转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 = A[i]; flag = TRUE; break; }l }l return flag;l }l算法的错误概率小于所给参数e算法的运转时间为O(nlog(1/e)) 。

7.7 蒙特卡罗〔蒙特卡罗〔Monte Carlo〕算法〕算法l素数测试 l一、普通方法l被测试的数除以2到   的数，余数为0，是合数，否那么是素数l二、蒙特卡罗算法 素数测试WilsonWilson定理：对于给定的正整数定理：对于给定的正整数定理：对于给定的正整数定理：对于给定的正整数n n，断定，断定，断定，断定n n是一个素数的充要条件是一个素数的充要条件是一个素数的充要条件是一个素数的充要条件是是是是(n-1)!(n-1)! -1(mod n) -1(mod n)费尔马小定理：假设费尔马小定理：假设费尔马小定理：假设费尔马小定理：假设p p是一个素数，且是一个素数，且是一个素数，且是一个素数，且0

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特性：特性：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 ，都有 ；l那么称断定问题π是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 Hard7.8 NP难与难与NP完全问题完全问题lNP完全问题的特性为：当且仅当一切其它NP完全问题可以在多项式时间内求解，该问题可以在多项式时间内求解l假设一个NP难问题可以在多项式时间内求解，那么一切的NP完全问题都可以在多项式时间内求解lNP完全和NP难问题都不是多项式时间可解的。