算法分析设计10-NP完全问题.ppt

《算法分析设计10-NP完全问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章NP完全问题学习要点：确定算法和不确定算法判定问题和最优化问题的关系可满足性问题P类问题和NP类问题NP难度(NPhard)和NP完全(NPcomplete)问题Cook定理典型的NP完全（或NP难度）问题的证明章节内容:10.1基本概念10.2.1Cook定理10.3一些典型的NP完全问题10.1基本概念将能在多项式时间内求解的问题视为易处理问题(tractableproblem)。至今尚未找到多项式时间算法求解的问题视为难处理问题(intractableproblem)。——NP完全问题或NP难度(NPhard)问

2、题——如：指数时间算法无论消耗多少计算机时间和空间也不能求解的称为不可判定(undecidable)的。——不存在任何算法求解如果任意一个NP难度问题存在一个多项式时间算法，那么所有NP完全问题都可以在多项式时间内求解。一个NP完全问题可以在多项式时间内求解，当且仅当所有其他的NP完全问题都可以在多项式时间内求解。10.1.1不确定算法和不确定机不确定算法的抽象计算模型：算法在抽象机上运行与计算机系统的性能无关；算法的执行表现为执行一个基本运算序列；基本运算的执行时间是有限常量；Choice(S)：任意选择集合S的一个元素。F

3、ailure()：发出不成功完成信号后算法终止。Success()：发出成功完成信号后算法终止。例10-1在n个元素的数组a中查找给定元素x，如果x在其中，则确定使a[j]==x的下标j，否则输出-1。不确定搜索算法：voidSearch(inta[],Tx){intj=Choice(0,n-1);//从{0,1,...,n-1}中任意选取一个值if(a[j]==x){cout<

4、一系列的Choice函数选择，当且仅当Choice的任何一组选择都不会导致成功信号时，算法在O(1)时间不成功终止。如果一个判定问题实例的解为真，Choice函数每一次总能在O(1)时间内做出导致成功的正确选择。包含不确定选择语句，并能按上述方式执行一个算法的机器称为不确定机（nondeterministicmachine)。在不确定机上执行的算法称为不确定算法(nondeterministicalgorithm)。不确定机的执行方式，可理解为不受限制的并行计算：不确定机执行不确定算法时，每当Choice函数进行选择时，就好像

5、复制了多个程序副本，每一种可能的选择产生一个副本，所有副本同时执行。一旦一个副本成功完成，将立即终止所有其他副本的计算。如果存在至少一种成功完成的选择，一台不确定机总能做出最佳选择，以最短的程序步数完成计算，并成功终止。不确定机能及时判断算法的某次执行不存在任何导致成功完成的选择，并使算法在一个单位时间内输出“不成功”信息后终止。显然，这种机器是虚构的，是一种概念性计算模型！不确定搜索算法：voidSearch(inta[],Tx){intj=Choice(0,n-1);if(a[j]==x){cout<

6、);}cout<<-1;Failure();}定义10-1（不确定算法时间复杂度）一个不确定算法所需的时间是指对任意一个输入，当存在一个选择序列导致成功完成时，达到成功完成所需的最少程序步。在不可能成功完成的情况下，所需时间总是O(1)。若元素x在数组中，Choice函数总能在O(1)时间内选中该元素下标，并成功终止。否则，算法在O(1)时间失败终止。因此该不确定搜索算法的时间复杂度为O(1)。例10-2将n个元素的序列排成有序序列。不确定排序算法：voidNSort(inta[],intn){intb[mSize],i,j;

7、for(i=0;ib[i+1])Failure();//若存在两元素逆序，则失败Success();//Choice函数的n次正确选择，算法成功}必定存在对b中下

8、标的n次恰当选择，使得能将每个a[i]恰好保存在一个空闲的b[j]处，并且进一步确保b中元素排成有序序列，从而能顺利通过随后的有序性验证，导致成功终止。因此该不确定搜索算法的时间复杂度为O(n)。判定问题和最优化问题一个只要求产生“0”或“1”作为输出的问题称为判定问题（de