《算法分析设计完全问题课件.ppt》由会员分享，可在线阅读，更多相关《算法分析设计完全问题课件.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法分析设计完全问题第1页，此课件共30页哦第10章 NP完全问题学学习习要点：要点：l l确定算法和不确定算法确定算法和不确定算法l l判定判定问题问题和最和最优优化化问题问题的关系的关系l l可可满满足性足性问题问题l lP P类问题类问题和和NPNP类问题类问题l lNPNP难难度度(NP hard)(NP hard)和和NPNP完全完全(NP complete)(NP complete)问题问题l lCookCook定理定理l l典型的典型的NPNP完全（或完全（或NPNP难难度）度）问题问题的的证证明明第2页，此课件共30页哦l l章节内容:10.1 10.1 基本概念基本概念10.
2、2.1 Cook10.2.1 Cook定理定理10.3 10.3 一些典型的一些典型的NPNP完全完全问题问题第3页，此课件共30页哦10.1 基本概念l l将能在多项式时间内求解的问题视为易处理问题(tractable problem)。l l至今尚未找到多项式时间算法求解的问题视为难处理问题(intractable problem)。NP完全问题或NP难度(NP hard)问题如：指数时间算法l l无论消耗多少计算机时间和空间也不能求解的称为不可判定(undecidable)的。不存在任何算法求解如果如果如果如果任意一个任意一个任意一个任意一个NPNP难难度度度度问题问题存在一个多存在一个
3、多存在一个多存在一个多项项式式式式时间时间算法，那么算法，那么算法，那么算法，那么所所所所有有有有NPNP完全完全完全完全问题问题都可以在多都可以在多都可以在多都可以在多项项式式式式时间时间内求解。内求解。内求解。内求解。一个一个一个一个NPNP完全完全完全完全问题问题可以在多可以在多可以在多可以在多项项式式式式时间时间内求解，当且内求解，当且内求解，当且内求解，当且仅仅当当当当所有所有所有所有其他的其他的其他的其他的NPNP完全完全完全完全问题问题都可以在多都可以在多都可以在多都可以在多项项式式式式时间时间内求解。内求解。内求解。内求解。第4页，此课件共30页哦10.1.1 不确定算法和不确
4、定机不确定算法的抽象计算模型：l l算法在抽象机上运行与计算机系统的性能无关；l l算法的执行表现为执行一个基本运算序列；l l基本运算的执行时间是有限常量；l lChoice(S)Choice(S)：任意：任意：任意：任意选择选择集合集合集合集合S S的一个元素。的一个元素。的一个元素。的一个元素。l lFailure()Failure()：发发出不成功完成信号后算法出不成功完成信号后算法出不成功完成信号后算法出不成功完成信号后算法终终止。止。止。止。l lSuccess()Success()：发发出成功完成信号后算法出成功完成信号后算法出成功完成信号后算法出成功完成信号后算法终终止。止。止
5、。止。第5页，此课件共30页哦例例例例10-110-1 在在在在n n个元素的数个元素的数个元素的数个元素的数组组a a中中中中查查找找找找给给定元素定元素定元素定元素x x，如果，如果，如果，如果x x在其在其在其在其中，中，中，中，则则确定使确定使确定使确定使aj=xaj=x的下的下的下的下标标j j，否，否，否，否则输则输出出出出-1-1。不确定搜索算法不确定搜索算法不确定搜索算法不确定搜索算法：void Search(int a,T x)void Search(int a,T x)int j=int j=Choice(0,n-1)Choice(0,n-1);/从从从从0,1,.,n-1
6、0,1,.,n-1中任意中任意中任意中任意选选取一个取一个取一个取一个值值 if(aj=x)if(aj=x)coutj;coutj;Success();Success();/不确定算法成功不确定算法成功不确定算法成功不确定算法成功终终止止止止 cout-1;cout-1;Failure();Failure();/不确定算法失不确定算法失不确定算法失不确定算法失败终败终止止止止 执行时间都为执行时间都为执行时间都为执行时间都为O(1)O(1)若算法执行中需作出一系列的若算法执行中需作出一系列的若算法执行中需作出一系列的若算法执行中需作出一系列的ChoiceChoice函数选择，函数选择，函数选择
7、，函数选择，当且仅当当且仅当当且仅当当且仅当ChoiceChoice的的的的任何一组选择都不会导致任何一组选择都不会导致任何一组选择都不会导致任何一组选择都不会导致成功信号时成功信号时成功信号时成功信号时，算法在，算法在，算法在，算法在O(1)O(1)时间不成功终止时间不成功终止时间不成功终止时间不成功终止。如果一个判定问题实例的解为真，如果一个判定问题实例的解为真，如果一个判定问题实例的解为真，如果一个判定问题实例的解为真，ChoiceChoice函数每一次总能在函数每一次总能在函数每一次总能在函数每一次总能在O(1)O(1)时间内做时间内做时间内做时间内做出导致成功的正确选择出导致成功的正
8、确选择出导致成功的正确选择出导致成功的正确选择。包含不确定包含不确定包含不确定包含不确定选择语选择语句，并能按上述方式句，并能按上述方式句，并能按上述方式句，并能按上述方式执执行一个算法的行一个算法的行一个算法的行一个算法的机器称机器称机器称机器称为为不确定机（不确定机（不确定机（不确定机（non deterministic machine)non deterministic machine)。在不确定机上在不确定机上在不确定机上在不确定机上执执行的算法称行的算法称行的算法称行的算法称为为不确定算法不确定算法不确定算法不确定算法(non(non deterministic algorithm)
9、deterministic algorithm)。第6页，此课件共30页哦不确定机不确定机不确定机不确定机的的的的执执行方式，可理解行方式，可理解行方式，可理解行方式，可理解为为不受限制的并行不受限制的并行不受限制的并行不受限制的并行计计算算算算：l l不确定机不确定机不确定机不确定机执执行行行行不确定算法不确定算法不确定算法不确定算法时时，每当，每当，每当，每当ChoiceChoice函数函数函数函数进进行行行行选择选择时时，就好像复制了多个程序副本，每一种可能的，就好像复制了多个程序副本，每一种可能的，就好像复制了多个程序副本，每一种可能的，就好像复制了多个程序副本，每一种可能的选择产选择
10、产生生生生一个副本，所有副本同一个副本，所有副本同一个副本，所有副本同一个副本，所有副本同时执时执行。行。行。行。一旦一个副本成功完成，一旦一个副本成功完成，一旦一个副本成功完成，一旦一个副本成功完成，将立即将立即将立即将立即终终止所有其他副本的止所有其他副本的止所有其他副本的止所有其他副本的计计算算算算。l l如果如果如果如果存在至少一种成功完成的存在至少一种成功完成的存在至少一种成功完成的存在至少一种成功完成的选择选择，一台不确定机，一台不确定机，一台不确定机，一台不确定机总总能做出最佳能做出最佳能做出最佳能做出最佳选择选择，以，以，以，以最短的程序步数最短的程序步数最短的程序步数最短的程
11、序步数完成完成完成完成计计算，并算，并算，并算，并成功成功成功成功终终止止止止。l l不确定机不确定机不确定机不确定机能及能及能及能及时时判断判断判断判断算法的某次算法的某次算法的某次算法的某次执执行行行行不存在任何不存在任何不存在任何不存在任何导导致成致成致成致成功完成的功完成的功完成的功完成的选择选择，并使算法在，并使算法在，并使算法在，并使算法在一个一个一个一个单单位位位位时间时间内内内内输输出出出出“不成功不成功不成功不成功”信息后信息后信息后信息后终终止。止。止。止。显然，这种机器是虚构的，是一种概念性计算模型！显然，这种机器是虚构的，是一种概念性计算模型！显然，这种机器是虚构的，是
12、一种概念性计算模型！显然，这种机器是虚构的，是一种概念性计算模型！第7页，此课件共30页哦不确定搜索算法不确定搜索算法不确定搜索算法不确定搜索算法：void Search(int a,T x)void Search(int a,T x)int j=int j=Choice(0,n-1)Choice(0,n-1);if(aj=x)if(aj=x)coutj;coutj;Success();Success();cout-1;cout-1;Failure();Failure();定定定定义义10-110-1 （不确定算法不确定算法不确定算法不确定算法时间时间复复复复杂杂度）度）度）度）一个不确定算法
13、所需的一个不确定算法所需的一个不确定算法所需的一个不确定算法所需的时间时间是指是指是指是指对对任意一个任意一个任意一个任意一个输输入，当存在一入，当存在一入，当存在一入，当存在一个个个个选择选择序列序列序列序列导导致致致致成功成功成功成功完成完成完成完成时时，达到成功完成，达到成功完成，达到成功完成，达到成功完成所需的最少程所需的最少程所需的最少程所需的最少程序步序步序步序步。在。在。在。在不可能成功完成不可能成功完成不可能成功完成不可能成功完成的情况下，所需的情况下，所需的情况下，所需的情况下，所需时间总时间总是是是是O(1)O(1)。若元素若元素若元素若元素x x在数组中，在数组中，在数组
14、中，在数组中，ChoiceChoice函数总函数总函数总函数总能在能在能在能在O(1)O(1)时间内选中该元素下标，时间内选中该元素下标，时间内选中该元素下标，时间内选中该元素下标，并并并并成功终止成功终止成功终止成功终止。否则，算法在否则，算法在否则，算法在否则，算法在O(1)O(1)时间时间时间时间失败终止失败终止失败终止失败终止。因此该不确定搜索算法的时间复杂因此该不确定搜索算法的时间复杂因此该不确定搜索算法的时间复杂因此该不确定搜索算法的时间复杂度为度为度为度为O(1)O(1)。第8页，此课件共30页哦例例例例10-210-2 将将将将n n个元素的序列排成有序序列。个元素的序列排成有
15、序序列。个元素的序列排成有序序列。个元素的序列排成有序序列。不确定排序算法不确定排序算法不确定排序算法不确定排序算法：void NSort(int a,int n)void NSort(int a,int n)int bmSize,i,j;int bmSize,i,j;for(i=0;in;i+)bi=0;for(i=0;in;i+)bi=0;/将将将将b b初始化初始化初始化初始化为为0 0 for(i=0;in;i+)for(i=0;in;i+)/将每个将每个将每个将每个aiai存放在一个空存放在一个空存放在一个空存放在一个空闲闲的的的的bjbj中中中中 j=j=Choice(0,n-1)
16、Choice(0,n-1);/任意任意任意任意选择选择一个下一个下一个下一个下标标if(bj)if(bj)FailureFailure;/若若若若bj0bj0，则则算法失算法失算法失算法失败终败终止止止止bj=ai;bj=ai;/将将将将aiai付付付付给给bjbj for(i=0;in-1;i+)for(i=0;ibi+1)if(bibi+1)Failure();Failure();/若存在两元素逆序，若存在两元素逆序，若存在两元素逆序，若存在两元素逆序，则则失失失失败败 Success();Success();/Choice/Choice函数的函数的函数的函数的n n次正确次正确次正确次正
17、确选择选择，算法成功，算法成功，算法成功，算法成功 必定存在对必定存在对必定存在对必定存在对b b中下标的中下标的中下标的中下标的n n次恰当选择，次恰当选择，次恰当选择，次恰当选择，使得能使得能使得能使得能将每个将每个将每个将每个aiai恰好保存在一个空恰好保存在一个空恰好保存在一个空恰好保存在一个空闲的闲的闲的闲的bjbj处处处处，并且，并且，并且，并且进一步确保进一步确保进一步确保进一步确保b b中元素中元素中元素中元素排成有序序列排成有序序列排成有序序列排成有序序列，从而能顺利通过随后，从而能顺利通过随后，从而能顺利通过随后，从而能顺利通过随后的有序性验证，导致的有序性验证，导致的有序
18、性验证，导致的有序性验证，导致成功终止成功终止成功终止成功终止。因此因此因此因此该不确定搜索算法的时间复杂度该不确定搜索算法的时间复杂度该不确定搜索算法的时间复杂度该不确定搜索算法的时间复杂度为为为为O(n)O(n)。第9页，此课件共30页哦判定问题和最优化问题一个只要求一个只要求一个只要求一个只要求产产生生生生“0”0”或或或或“1”1”作作作作为输为输出的出的出的出的问题问题称称称称为为判定判定判定判定问题问题（decision problemdecision problem）。）。）。）。许许多多多多最最最最优优化化化化问题问题都可以得到与其相都可以得到与其相都可以得到与其相都可以得到与
19、其相对应对应的的的的判定判定判定判定问题问题，且两者，且两者，且两者，且两者往往存在往往存在往往存在往往存在计计算上的相关性：算上的相关性：算上的相关性：算上的相关性：一个一个一个一个判定判定判定判定问题问题能能能能够够在多在多在多在多项项式式式式时间时间内求解，内求解，内求解，内求解，当且当且当且当且仅仅当当当当它相它相它相它相应应的的的的最最最最优优化化化化问题问题可以在多可以在多可以在多可以在多项项式式式式时间时间内求解。内求解。内求解。内求解。如果如果如果如果判定判定判定判定问题问题不能在多不能在多不能在多不能在多项项式式式式时间时间内求解，那么它相内求解，那么它相内求解，那么它相内求
20、解，那么它相应应的的的的最最最最优优化化化化问题问题也不能在多也不能在多也不能在多也不能在多项项式式式式时间时间内求解。内求解。内求解。内求解。第10页，此课件共30页哦例例例例10-3 10-3 最大集最大集最大集最大集团团及其判定及其判定及其判定及其判定问题问题无向无向无向无向图图G=G=（V,EV,E）的一个完全子）的一个完全子）的一个完全子）的一个完全子图图称称称称为该图为该图的一个的一个的一个的一个集集集集团团，集集集集团团的的的的规规模模模模用集用集用集用集团团的的的的顶顶点数衡量。点数衡量。点数衡量。点数衡量。l l最大集最大集最大集最大集团问题团问题：确定确定确定确定图图GG的
21、最大集的最大集的最大集的最大集团规团规模模模模的的的的问题问题。l l最大集最大集最大集最大集团团判定判定判定判定问题问题：判定判定判定判定图图GG是否存在一个是否存在一个是否存在一个是否存在一个规规模至少模至少模至少模至少为为k k的集的集的集的集团团。（。（。（。（k k为给为给定正整数）定正整数）定正整数）定正整数）第11页，此课件共30页哦若若若若最大集最大集最大集最大集团问题团问题能在能在能在能在多多多多项项式式式式时间时间O(g(n)O(g(n)内求解。内求解。内求解。内求解。当且当且当且当且仅仅当当当当对应对应的的的的判定判定判定判定问题问题能在能在能在能在多多多多项项式式式式时
22、间时间O(f(n)O(f(n)内求解。内求解。内求解。内求解。一方面：只需以一方面：只需以一方面：只需以一方面：只需以k=1,2,.,nk=1,2,.,n，最多最多最多最多n n次次次次调调用最大集用最大集用最大集用最大集团团判定算法判定算法判定算法判定算法，便可便可便可便可求得最大集求得最大集求得最大集求得最大集团团的大小的大小的大小的大小，因此，因此，因此，因此O(g(n)=O(nf(n)O(g(n)=O(nf(n)；另一方面：可另一方面：可另一方面：可另一方面：可使用求解最大集使用求解最大集使用求解最大集使用求解最大集团问题团问题的算法的算法的算法的算法，求得最大集，求得最大集，求得最大
23、集，求得最大集团团的的的的规规模模模模为为kk。若若若若kkkk，则则最大集最大集最大集最大集团团判定判定判定判定问题问题的解的解的解的解为为“1”1”，否，否，否，否则则为为“0”0”。显显然有然有然有然有O(f(n)=O(g(n)O(f(n)=O(g(n)。许许多抽象多抽象多抽象多抽象问题问题并不是判定并不是判定并不是判定并不是判定问题问题，而是最，而是最，而是最，而是最优优化化化化问题问题，必，必，必，必须须最最最最大化或最小化某个量。然而，如我大化或最小化某个量。然而，如我大化或最小化某个量。然而，如我大化或最小化某个量。然而，如我们们看到的，看到的，看到的，看到的，将最将最将最将最优
24、优化化化化问题转问题转化化化化为为一个并不更一个并不更一个并不更一个并不更难难的判定的判定的判定的判定问题问题通常是比通常是比通常是比通常是比较简单较简单的的的的。第12页，此课件共30页哦10.1.2 可满足性问题l l数理数理逻辑中，一个中，一个变量量 和它的非和它的非 都称都称为文字文字。l l命命题公式公式是由是由文字文字及及逻辑运算符运算符“与与()”和和“或或()”构成的表达式。构成的表达式。l l如果一个公式具有如果一个公式具有如果一个公式具有如果一个公式具有逻辑逻辑与形式：与形式：与形式：与形式：C C1 1C C2 2.C Ck k，其中，其中，其中，其中每个子句每个子句每个
25、子句每个子句C Ci i都是都是都是都是逻辑逻辑或形式或形式或形式或形式l li1i1l li2i2.l lipip，每个，每个，每个，每个l lij ij是文是文是文是文字，字，字，字，则则将将将将这这种形式的公式称种形式的公式称种形式的公式称种形式的公式称为为合取范式合取范式合取范式合取范式(conjunctive(conjunctive normal formnormal form，CNFCNF)。l l如果一个公式具有如果一个公式具有如果一个公式具有如果一个公式具有逻辑逻辑或形式：或形式：或形式：或形式：C C1 1C C2 2.C Ck k，其中，其中，其中，其中每个子句每个子句每个
26、子句每个子句C Ci i都是都是都是都是逻辑逻辑与形式与形式与形式与形式l li1i1l li2 i2.l liqiq，每个，每个，每个，每个l lij ij是文字，是文字，是文字，是文字，则则将将将将这这种形式的公式称种形式的公式称种形式的公式称种形式的公式称为为析取范式析取范式析取范式析取范式(disjunctive normal(disjunctive normal formform，DNFDNF)。第13页，此课件共30页哦例例例例10-4 10-4 可可可可满满足性足性足性足性问题问题（satisfiability problem)satisfiability problem)是一个
27、是一个是一个是一个判定判定判定判定问题问题，确定，确定，确定，确定对对于一个于一个于一个于一个给给定的命定的命定的命定的命题题公式公式公式公式，是否，是否，是否，是否存在布存在布存在布存在布尔变尔变量的一种量的一种量的一种量的一种赋值赋值（也称（也称（也称（也称真真真真值值指派指派指派指派）使）使）使）使该该公式公式公式公式为为真。真。真。真。例如：例如：例如：例如：公式公式公式公式是可是可是可是可满满足的。只需令足的。只需令足的。只需令足的。只需令x x1 1=1=1，x x2 2=0=0，x x3 3=0=0。公式公式是是不可可满足的。足的。第14页，此课件共30页哦程序程序程序程序10-
28、4 10-4 可可可可满满足性足性足性足性问题问题的不确定算法的不确定算法的不确定算法的不确定算法void Eval(CNF E,int n)void Eval(CNF E,int n)int xmSize;int xmSize;for(int i=1;i=n;i+)for(int i=1;i=n;i+)/O(n)O(n)xi=xi=Choice(0,1);Choice(0,1);/为变为变量量量量xixi赋赋0 0或或或或1 1值值 if(E(x,n)if(E(x,n)Success();Success();/O(e)O(e)，计计算公式算公式算公式算公式E(x,n)E(x,n)的的的的值值
29、/若若若若为为真，成功真，成功真，成功真，成功终终止止止止 else else Failure();Failure();因因因因为为：对对n n个布个布个布个布尔变尔变量量量量赋值赋值需要需要需要需要O(n)O(n)时间时间，计计算公式算公式算公式算公式E(x,n)E(x,n)的的的的时间为时间为O(e)O(e)，e e是公式是公式是公式是公式长长度。度。度。度。所以，可所以，可所以，可所以，可满满足性足性足性足性问题问题的不确定算法的不确定算法的不确定算法的不确定算法时间为时间为O(n+e)O(n+e)。第15页，此课件共30页哦10.1.3 P类和NP类问题P P类类问题问题：可在多：可在
30、多：可在多：可在多项项式式式式时间时间内用内用内用内用确定算法求解确定算法求解确定算法求解确定算法求解的判定的判定的判定的判定问问题题。NPNP类类问题问题：可在多：可在多：可在多：可在多项项式式式式时间时间内用内用内用内用不确定算法求解不确定算法求解不确定算法求解不确定算法求解的判定的判定的判定的判定问题问题。（多。（多。（多。（多项项式式式式时间时间内内内内可可可可验证验证问题问题的解。）的解。）的解。）的解。）确定算法确定算法是是不确定算法不确定算法当当Choice函数只有一种函数只有一种选择时的特例的特例，所以有：，所以有：但至今无法断定：是否但至今无法断定：是否P=NP或者或者PNP
31、。第16页，此课件共30页哦定定定定义义10-3 10-3 多多多多项项式式式式约约化化化化令令令令QQ1 1和和和和QQ2 2是两个是两个是两个是两个问题问题，如果存在一个，如果存在一个，如果存在一个，如果存在一个确定算法确定算法确定算法确定算法A A求解求解求解求解QQ1 1，而算法，而算法，而算法，而算法A A以多以多以多以多项项式式式式时间调时间调用用用用另一个另一个另一个另一个求解求解求解求解QQ2 2的确定算法的确定算法的确定算法的确定算法B B。若不若不若不若不计计B B的工作量，算法的工作量，算法的工作量，算法的工作量，算法A A是多是多是多是多项项式式式式时间时间的，的，的，
32、的，则则称称称称QQ1 1约约化化化化(reduced to)(reduced to)为为QQ2 2，记记作作作作QQ1 1 QQ2 2。即：即：l求解求解Q1的确定算法是通的确定算法是通过调用求解用求解Q2的确定算法完的确定算法完成的，成的，l对Q2算法算法实施的施的调用用过程所需的程所需的时间是多是多项式式时间的。的。那么：那么：只要只要对问题Q2存在多存在多项式式时间求解算法，求解算法，问题Q1就能在多就能在多项式式时间内得以求解。内得以求解。第17页，此课件共30页哦约约化化化化存在以下存在以下存在以下存在以下性性性性质质：性性性性质质10-110-1 若若若若QQ1 1 P P，QQ
33、2 2 QQ1 1，则有，则有，则有，则有QQ2 2 P P。性性性性质质10-2 10-2（传递性）（传递性）（传递性）（传递性）若若若若QQ1 1 QQ2 2，QQ2 2 QQ3 3，则，则，则，则QQ1 1 QQ3 3。第18页，此课件共30页哦10.1.4 NP难度和NP完全问题性性性性质质10-4 NP10-4 NP难难度（度（度（度（NP hardNP hard）对对任意任意任意任意问题问题QQ1 1NPNP都有都有都有都有QQ1 1QQ，则称问题，则称问题，则称问题，则称问题QQ是是是是NPNP难度难度难度难度（NP hardNP hard）的。）的。）的。）的。只要只要只要只要
34、对对任何一个任何一个任何一个任何一个NPNP难难度度度度问题问题QQ找到了它的多找到了它的多找到了它的多找到了它的多项项式式式式时间时间算法，算法，算法，算法，那么，可以断定那么，可以断定那么，可以断定那么，可以断定所有所有所有所有NPNP类问题类问题都能在多都能在多都能在多都能在多项项式式式式时间时间内求解，内求解，内求解，内求解，因因因因为为所有所有所有所有NPNP类问题类问题都能都能都能都能约约化到化到化到化到问题问题QQ。（然而（然而（然而（然而目前尚无任何一个目前尚无任何一个目前尚无任何一个目前尚无任何一个NPNP难难度度度度问题问题具有多具有多具有多具有多项项式式式式时间时间算法。
35、算法。算法。算法。）第19页，此课件共30页哦性性性性质质10-5 NP10-5 NP完全（完全（完全（完全（NP completeNP complete）对对于于于于问题问题QQ NPNP且且且且QQ是是是是NPNP难度的难度的难度的难度的，则称，则称，则称，则称QQ是是是是NPNP完全完全完全完全（NP NP completecomplete，NPCNPC）的。）的。）的。）的。所有所有所有所有NPNP完全完全完全完全问题问题都是都是都是都是NPNP难难度的度的度的度的，反之不然，反之不然，反之不然，反之不然，NPNP难难度度度度问问题题不一定是不一定是不一定是不一定是NPNP完全的完全的
36、完全的完全的（若不是（若不是（若不是（若不是NPNP类问题类问题，则则不是不是不是不是NPNP完完完完全的）。全的）。全的）。全的）。第20页，此课件共30页哦现实现实意意意意义义：若一个若一个若一个若一个问题问题被被被被证证明是明是明是明是NPNP难难度（度（度（度（NP hardNP hard）的，的，的，的，则则很很很很难难找到找到找到找到一个多一个多一个多一个多项项式式式式时间时间的有效算法。若的有效算法。若的有效算法。若的有效算法。若问题问题的的的的实实例例例例规规模模模模较较大，大，大，大，则应则应选择选择采用采用采用采用启启启启发发式算法式算法式算法式算法、随机算法或近似算法等其
37、他算法、随机算法或近似算法等其他算法、随机算法或近似算法等其他算法、随机算法或近似算法等其他算法策略求解。策略求解。策略求解。策略求解。如何确定某个如何确定某个如何确定某个如何确定某个问题问题是否是是否是是否是是否是NPNP难难度度度度的？的？的？的？第21页，此课件共30页哦证证明某个明某个明某个明某个问题问题QQ是是是是NPNP难难度（度（度（度（NP hardNP hard）的的的的证证明策略明策略明策略明策略：(1)(1)选择选择一个一个一个一个已已已已经证经证明是明是明是明是NPNP难难度度度度问题问题QQ1 1;(2)(2)求求求求证证QQ1 1QQ。则问题则问题QQ是是是是NPN
38、P难难度度度度的。的。的。的。l l由于由于由于由于QQ1 1是是是是NPNP难难度的，因此所有度的，因此所有度的，因此所有度的，因此所有NPNP类问题类问题都可都可都可都可约约化到化到化到化到QQ1 1。l l根据根据根据根据约约化的化的化的化的传递传递性，任何性，任何性，任何性，任何NPNP类问题类问题都可都可都可都可约约化到化到化到化到QQ。l l所以，所以，所以，所以，QQ是是是是NPNP难难度的。度的。度的。度的。在此基在此基在此基在此基础础上，若上，若上，若上，若进进一步表明一步表明一步表明一步表明QQ本身是本身是本身是本身是NPNP类类的，的，的，的，则问题则问题QQ是是是是NP
39、NP完全完全完全完全的。的。的。的。第22页，此课件共30页哦10.2 Cook定理和证明10.2.1 Cook定理斯蒂芬斯蒂芬斯蒂芬斯蒂芬 库库克（克（克（克（Steven CookSteven CookSteven CookSteven Cook）于）于）于）于1971197119711971年年年年证证明了第一个明了第一个明了第一个明了第一个NPNPNPNP完全完全完全完全问题问题，称，称，称，称为为CookCookCookCook定理定理定理定理，表明，表明，表明，表明可可可可满满足性足性足性足性问题问题是是是是NPNPNPNP完全的。完全的。完全的。完全的。至今至少已有至今至少已有至
40、今至少已有至今至少已有300300300300多个多个多个多个问题问题被被被被证证明是明是明是明是NPNPNPNP难难度度度度问题问题，但，但，但，但尚未尚未尚未尚未证证明其中任何一个是明其中任何一个是明其中任何一个是明其中任何一个是属于属于属于属于P P P P的。的。的。的。第23页，此课件共30页哦10.3 一些典型的NP完全问题证证明明(一个猜想可能是一个猜想可能是NPNP难难度的度的)问题问题Q Q确确实实是是NPNP难难度度(或或NPNP完全完全)问题问题的具体步的具体步骤骤：利用利用多多项项式式约约化化（归约归约）的方法的方法（1 1）选择选择一个一个已知其具有已知其具有NPNP
41、难难度的度的问题问题Q Q1 1；（2 2）证证明能明能够够从从Q Q1 1的一个的一个实实例例I I1 1，在多，在多项项式式时间时间内构造内构造Q Q的的一个一个实实例例I I；（3 3）证证明能明能够够在多在多项项式式时间时间内从内从I I的解确定的解确定I I1 1的解的解。（4 4）从（）从（2 2）和（）和（3 3）可知，）可知，Q Q1 1 Q Q；（5 5）从（）从（1 1）和（）和（4 4）及）及约约化的化的传递传递性得出所有性得出所有NPNP类问题类问题均可均可约约化到化到Q Q，所以所以Q Q是是NPNP难难度的度的。（6 6）*如果如果Q Q是是NPNP类类问题问题，则
42、则Q Q是是NPNP完全完全的。的。第24页，此课件共30页哦10.3.1 最大集团最大集最大集最大集最大集团团判定判定判定判定问题问题是是是是NPNP类类问题问题。“集集集集团团”是无向是无向是无向是无向图图中的中的中的中的完全子完全子完全子完全子图图，任意一，任意一，任意一，任意一对顶对顶点点点点间间有有有有边边相相相相连连。P231 P231 程序程序程序程序10-310-3是是是是求解求解求解求解该问题该问题的的的的多多多多项项式式式式时间时间不确定算法不确定算法不确定算法不确定算法。或：或：或：或：对给对给定的定的定的定的图图G=(V,E)G=(V,E)，检查顶检查顶点点点点集集集集
43、V VV V中每一中每一中每一中每一对顶对顶点点点点u,vu,v间间是否是否是否是否存在存在存在存在边边(u,v)(u,v)E E，即可在，即可在，即可在，即可在多多多多项项式式式式时间时间内内内内完成完成完成完成对对VV是否是集是否是集是否是集是否是集团团的的的的检检查查。第25页，此课件共30页哦最大集最大集最大集最大集团团判定判定判定判定问题问题是是是是NPNP完全完全完全完全的。的。的。的。下面下面下面下面证证明：明：明：明：证证明思路：明思路：明思路：明思路：l l证证明明明明CNFCNF可可可可满满足性足性足性足性最大集最大集最大集最大集团团判定判定判定判定问题问题，所以最，所以最
44、，所以最，所以最大集大集大集大集团团判定判定判定判定问题问题是是是是NPNP难难度度度度的。的。的。的。l l又因又因又因又因为为最大集最大集最大集最大集团团判定判定判定判定问题问题是是是是NPNP类类问题问题（前面已（前面已（前面已（前面已证证）所以所以所以所以最大集最大集最大集最大集团团判定判定判定判定问题问题是是是是NPNP完全完全完全完全的。的。的。的。第26页，此课件共30页哦定理定理定理定理10-3 CNF10-3 CNF可可可可满满足性足性足性足性最大集最大集最大集最大集团团判定判定判定判定问题问题证证明：明：明：明：1 1、在、在、在、在多多多多项项式式式式时间时间内内内内，以
45、任意，以任意，以任意，以任意给给定的定的定的定的CNFCNF公式公式公式公式F F为为输输入，入，入，入，构造构造构造构造一个相一个相一个相一个相应应的的的的无向无向无向无向图图GG；2 2、证证明明明明F F是可是可是可是可满满足的，足的，足的，足的，当且当且当且当且仅仅当当当当GG有一个有一个有一个有一个规规模至模至模至模至少少少少为为k k的集的集的集的集团团。第27页，此课件共30页哦定理定理定理定理10-3 CNF10-3 CNF可可可可满满足性足性足性足性最大集最大集最大集最大集团团判定判定判定判定问题问题证证明：明：明：明：1 1、在多、在多、在多、在多项项式式式式时间时间内，以
46、任意内，以任意内，以任意内，以任意给给定的定的定的定的CNFCNF公式公式公式公式F F为输为输入，入，入，入，构造构造构造构造一个相一个相一个相一个相应应的的的的无向无向无向无向图图GG；令令令令F=CF=C1 1 C C2 2 .C Ck k是一个具有是一个具有是一个具有是一个具有k k个子句个子句个子句个子句的的的的CNFCNF形式的布形式的布形式的布形式的布尔尔公式。公式。公式。公式。由公式由公式由公式由公式F F构造无向构造无向构造无向构造无向图图GG的方法的方法的方法的方法为为：V=V=|是子句是子句是子句是子句C Ci i的一个文字的一个文字的一个文字的一个文字 E=(E=(,)
47、|)|ijij 且且且且 属于哪个子句属于哪个子句 和和和和 处处于于于于不同的分句中不同的分句中不同的分句中不同的分句中 和和和和 相相相相应应的文字的文字的文字的文字是一致的是一致的是一致的是一致的第28页，此课件共30页哦如：如：如：如：则则GG就是下就是下就是下就是下图图：第29页，此课件共30页哦定理定理定理定理10-3 CNF10-3 CNF可可可可满满足性足性足性足性最大集最大集最大集最大集团团判定判定判定判定问题问题证证明：明：明：明：2 2、证证明明明明F F是可是可是可是可满满足的，足的，足的，足的，当且当且当且当且仅仅当当当当GG有一个有一个有一个有一个规规模至少模至少模
48、至少模至少为为k k的的的的集集集集团团。（一方面，如果（一方面，如果（一方面，如果（一方面，如果F F可可可可满满足，足，足，足，那么那么那么那么图图GG中必定存在中必定存在中必定存在中必定存在规规模模模模为为k k的集的集的集的集团团。）。）。）。）若若若若F F是可是可是可是可满满足的，足的，足的，足的，则则必定存在布必定存在布必定存在布必定存在布尔变尔变量的一个量的一个量的一个量的一个赋值赋值，使，使，使，使F F的的的的每每每每个子句个子句个子句个子句C Ci i中至少有一个文字中至少有一个文字中至少有一个文字中至少有一个文字为为真真真真。若。若。若。若 i i是子句是子句是子句是子
49、句C Ci i中中中中为为真的真的真的真的文字，文字，文字，文字，则则S S=,1,2,.,.,k 是是是是图图GG中相中相中相中相应顶应顶点点点点集合集合集合集合。根据根据根据根据图图的构造方法的构造方法的构造方法的构造方法，集合，集合，集合，集合S S中任意一中任意一中任意一中任意一对顶对顶点点点点,i和和和和,j，由于，由于，由于，由于 i i和和和和 j j都都都都为为真且真且真且真且i i j j，因此，因此，因此，因此它它它它们们之之之之间应该间应该有有有有边边相相相相连连，从而形成完全，从而形成完全，从而形成完全，从而形成完全图图。S S就是就是就是就是图图GG的的的的规规模模模模为为k k的集的集的集的集团团。第30页，此课件共30页哦