算法10_NP完全问题

算法设计与分析张怡婷Email:zyt@http://www.77cn.com.cn

第10章 NP完全问题

学习要点： 确定算法和不确定算法 判定问题和最优化问题的关系 可满足性问题 P类问题和NP类问题 NP难度(NP hard)和NP完全(NP complete)问题 Cook定理 典型的NP完全(或NP难度)问题的证明

ch10.2

章节内容:10.1 基本概念 10.2.1 Cook定理 10.3 一些典型的NP完全问题

ch10.3

10.1 基本概念将能在多项式时间内求解的问题视为易处理 问题(tractable problem)。 至今尚未找到多项式时间算法求解的问题视 为难处理问题(intractable problem)。 ——NP完全问题或NP难度(NP hard)问题 ——如：指数时间算法 如果任意一个NP难度问题存在一个多项式时间算法， 无论消耗多少计算机时间和空间也不能求解 那么所有NP完全问题都可以在多项式时间内求解。 的称为不可判定(undecidable)的。 一个NP完全问题可以在多项式时间内求解，当且仅 ——不存在任何算法求解

当所有其他的NP完全问题都可以在多项式时间内求解。 ch10.4

10.1.1 不确定算法和不确定机不确定算法的抽象计算模型： 算法在抽象机上运行与计算机系统的性能无 关； 算法的执行表现为执行一个基本运算序列； 基本运算的执行时间是有限常量； Choice(S):任意选择集合S的一个元素。 Failure():发出不成功完成信号后算法终止。 Success():发出成功完成信号后算法终止。ch10.5

包含不确定选择语句，并能按上述方式执行一个算法 例10-1 在n个元素的数组a中查找给定元素x,如果x 的机器称为不确定机(non deterministic machine)。 在其中，则确定使a[j]==x的下标j,否则输出-1。 在不确定机上执行的算法称为不确定算法(non 不确定搜索算法： deterministic algorithm)。 void Search(int a[],T x) 如果一个判定问题实例的解为真，{int j=Choice(0,n-1); if(a[j]==x) 执行时间都为O(1) { cout<<j; Success(); //不确定算法成功终止 } cout<<-1; 若算法执行中需作出一系列的Choice函 Failure(); //不确定算法失败终止 数选择，当且仅当Choice的任何一组选 } Choice函数每一次总能在O(1)时 间内做出导致成功的正确选择。 //从{0,1,...,n-1}中任意选取一个值

择都不会导致成功信号时，算法在O(1) 时间不成功终止。 ch10.6

不确定机的执行方式，可理解为不受限制的并行计算： 不确定机执行不确定算法时，每当Choice函数进 行选择时，就好像复制了多个程序副本，每一种可能 的选择产生一个副本，所有副本同时执行。一旦一个 副本成功完成，将立即终止所有其他副本的计算。 如果存在至少一种成功完成的选择，一台不确定机 总能做出最佳选择，以最短的程序步数完成计

算，并 成功终止。

不确定机能及时判断算法的某次执行不存在任何导 致成功完成的选择，并使算法在一个单位时间内输出 “不成功”信息后终止。显然，这种机器是虚构的，是一种概念性计算模型！ch10.7

定义10-1 (不确定算法时间复杂度) 一个不确定算法所需的时间是指对任意一个输入， 当存在一个选择序列导致成功完成时，达到成功完 成所需的最少程序步。在不可能成功完成的情况下， 所需时间总是O(1)。不确定搜索算法：void Search(int a[],T x) { int j=Choice(0,n-1); if(a[j]==x) { cout<<j; Success(); } cout<<-1; Failure(); }

若元素x在数组中，Choice函数总 能在O(1)时间内选中该元素下标， 并成功终止。 否则，算法在O(1)时间失败终止。 因此该不确定搜索算法的时间复杂 度为O(1)。 ch10.8

例10-2 将n个元素的序列排成有序序列。 不确定排序算法：void NSort(int a[],int n) { int b[mSize],i,j; for (i=0;i<n;i++) b[i]=0; //将b初始化为0 必定存在对b中下标的n次恰当选择， for (i=0;i<n;i++) //将每个a[i]存放在一个空闲的b[j]中 { j=Choice(0,n-1); 使得能将每个a[i]恰好保存在一个空 //任意选择一个下标 闲的b[j]处，并且进一步确保b中元素 if (b[j]) Failure; //若b[j]≠0,则算法失败终止 排成有序序列，从而能顺利通过随后 b[j]=a[i]; //将a[i]付给b[j] 的有序性验证，导致成功终止。 } 因此该不确定搜索算法的时间复杂度 for (i=0;i<n-1;i++) 为O(n)。 //验证b中元素是否已经有序 if (b[i]>b[i+1]) Failure(); //若存在两元素逆序，则失败 Success(); //Choice函数的n次正确选择，算法成功 ch10.9 }

判定问题和最优化问题一个只要求产生“0”或“1”作为输出的问题称为判 定问题(decision problem)。 许多最优化问题都可以得到与其相对应的判定问题， 且两者往往存在计算上的相关性： 一个判定问题能够在多项式时间内求解，当且仅当 它相应的最优化问题可以在多项式时间内求解。 如果判定问题不能在多项式时间内求解，那么它相 应的最优化问题也不能在多项式时间内求解。ch10.10

例10-3 最大集团及其判定问题 无向图G=(V,E)的一个完全子图称为该图的一个 集团，集团的规模用集团的顶点数衡量。

最大集团问题：确定图G的最大集团规模的问题。 最大集团判定问题：判定图G是否存在一个规模 至少为k的集团。(k为给定正整数)

ch10.11

若最大集团问题能在多项式时间O(g(n))内求解。 当且仅当 对应的判定问题能在多项式时间O(f(n))内求解。 一方面：只需以k=1,2,...,n,最多n次调用最大集团判 定算法，便可求得最大集团的大小，因此 O(g(n))=O(nf(n)); 另一方面：可使用求解 …… 此处隐藏：1846字，全部文档内容请下载后查看。喜欢就下载吧 ……