《第十二章NP完全问题.doc》由会员分享，可在线阅读，更多相关《第十二章NP完全问题.doc（18页珍藏版）》请在金锄头文库上搜索。
1、第十二章 NP完全问题一、易解的问题和难解的问题存在多项式时间算法的问题，称为易解的问题指数时间算法或排列时间算法的问题，称为难解的问题二、难解问题的计算相关性计算相关：某类问题可以归约为另一类问题计算相关的问题，若它们之一可用多项式时间求解，则其它同类问题也可用多项式时间求解；若它们之一肯定不存在多项式时间算法，则同类的其它问题，也肯定不会找到多项式时间算法。三、判定问题和优化问题1、判定问题只牵涉到两种情况：或，可以容易地表达为语言的识别问题，方便地在图灵机上进行求解。例：排序问题的判定问题：给定一个整数数组，是否可以按非降顺序排序；图着色的判定问题：给定无向图，是否可用种颜色为中的每一个
2、顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色。2、优化问题牵涉到极值问题例：图着色的优化问题：为图着色，使相邻两个顶点不会有相同颜色时所需要的最少颜色数目。3、判定问题转换为优化问题。例：求解为图着色，使相邻两个顶点不会有相同颜色时所需最少颜色数。令图的顶点个数为，彩色数是，假定存在一个图着色判定问题的多项式时间算法coloring： BOOL coloring(GRAPH G,int n,int num)则可用下面的方法，利用算法coloring来解图着色的优化问题。void chromatic_number(GRAPH G,int n,int &num)int high,low;
3、high = n;low = 1;while (low=high) num = (low + high) / 2; if (coloring(G,n,num) low = mid + 1; else high = mid 1;num = high;对算法coloring调用次，就能找出为图着色的最优彩色数。根据假定，coloring是多项式时间算法，所以，这个算法也是一个多项式时间算法。12.1 P类和NP类问题12.1.1 P类问题一、确定性算法定义12.1 是问题的一个算法。如果在处理问题的实例时，在算法的整个执行过程中，每一步只有一个确定的选择，就说算法是确定性的算法。算法执行的每一个步
4、骤，都有确定的选择。重新用同一输入实例运行该算法，所得到的结果严格一致。二、类判定问题1、定义：定义12.2 如果对某个判定问题，存在着一个非负整数，对输入规模为的实例，能够以的时间运行一个确定性的算法，得到或的答案，则该判定问题是一个类判定问题。2、特性：类判定问题是由具有多项式时间的确定性算法来解的判定问题例： 最短路径判定问题SHORTEST PATH：给定有向赋权图（权为正整数）、正整数、及两个顶点，是否存在着一条由到、长度至多为的路径。可排序的判定问题SORT：给定个元素的数组，是否可以按非降顺序排序。 三、封闭1、类判定问题的补：改变判定问题的提法，“是否可以”、“是否存在”改为“
5、是否不可以”、“是否不存在”的判定问题。例：可排序判定问题的补NOT_SORT：给定个元素的数组，是否不可以按非降顺序排序。最短路径判定问题的补NOT SHORTEST PATH：给定有向赋权图（权为正整数）、正整数、及两个顶点，是否不存在一条由到、长度至多为的路径。2、封闭的定义定义12.3 令是一类问题，如果对中的任何问题，的补也在中，则称类问题在补集下封闭。3、类问题的封闭性定理12.1 类问题在补集下是封闭的。证明 令类判定问题的补为；存在确定性算法，可用多项式时间返回或的答案。算法是算法中返回的代码改为返回、返回的代码，改为返回的算法。则算法是解问题的确定性算法，可用多项式时间返回或
6、的答案。因此类问题的补，也属于类问题。所以，类问题在补集下是封闭的。四、归约1、归约的定义定义12.4 令和是两个判定问题，如果存在一个具有如下性能的确定性算法，可以用多项式的时间，把问题的实例转换为问题的实例，使得的答案为，当且仅当的答案是。就说，以多项式时间归约于，记为。2、类问题的归约性定理12.2 和是两个判定问题，如果，并且，则。证明 因为，存在确定性算法，可用多项式时间，把问题的实例转换为问题的实例。使得的答案为，当且仅当的答案是。如果对某个正整数，算法每一步的输出，最多可输出个符号，则算法的输出规模，最多不会超过个符号。因为，存在多项式时间的确定性算法，对输入规模为的问题进行求解
7、。所得结果也是问题的结果。令算法是把算法和算法合并起来的算法，则算法也是确定性的算法，且以多项式时间得到问题的结果，所以，。12.1.2 NP类问题一、非确定性算法1、问题的非确定性算法的两个阶段：推测阶段和验证阶段。2、推测阶段：对规模为的输入实例，以多项式时间产生输出，而不管的正确性3、验证阶段：以多项式时间的确定性算法验证两件事情：1）检查上一阶段的输出是否具有正确的形式。如果不具正确的形式，算法就以答案结束；2）如果具有正确的形式，则继续检查是否是问题的输入实例的解。如果它确实是问题实例的解，则以答案结束，否则，以答案结束。例12.1 货郎担的判定问题：给定个城市、正常数、及城市之间的
8、费用矩阵，判定是否存在一条经过所有城市一次且仅一次、最后返回初始出发城市、且费用小于常数的回路。令是求解货郎担判定问题的算法。用非确定性的方法，在多项式时间内推测存在着一条回路，假定它是问题的解，用确定性的算法，在多项式时间内检查：该回路是否是哈密尔屯回路，如果答案为，则继续检查该回路的费用是否小于常数，如果答案仍为，则算法输出，否则输出。因此，是求解货郎担判定问题的非确定性算法。4、非确定性算法的运行时间，是推测阶段和验证阶段运行时间的和。若推测阶段的运行时间为，验证阶段的运行时间为，则对某个非负整数，非确定性算法的运行时间为。二、类判定问题1、定义：定义12.5 如果对某个判定问题，存在着
9、一个非负整数，对输入规模为的实例，能够以的时间运行一个非确定性的算法，得到或的答案，则该判定问题是一个类判定问题。2、特性：存在确定性的算法，能够以多项式时间，来检查和验证在推测阶段产生的答案。例12.2 解货郎担判定问题TRAVELING SALESMAN的算法：可在推测阶段用多项式时间推测出一条回路，并假定它是问题的解；在验证阶段用多项式时间的确定性算法，检查所推测的回路是否恰好每个城市经过一次，如果是，再进一步判断这条回路的长度是否小于或等于，如果是，答案为，否则，答案为。存在多项式时间的确定性算法，对推测阶段所作出的推测进行检查和验证。因此，货郎担判定问题是类判定问题。例12.3 团问
10、题CLIQUE：给定无向图、正整数，判定中是否存在个顶点，使得它们的导出子图构成完全图。在推测阶段用多项式时间对顶点集生成一组个顶点的子集，假定它是问题的解；在验证阶段用多项式时间的确定性算法，验证该子集的导出子图是否构成完全图。如果是，答案为，否则，答案为。存在多项式时间的确定性算法，对前面的推测进行检查和验证。因此，团问题是类判定问题。3、类问题和类问题的差别：类问题可以用多项式时间的确定性算法来进行判定或求解；类问题可以用多项式时间的确定性算法来检查和验证它的解。，必然有，所以，。猜测。该不等式是否成立、至今还没有得到证明。12.2 NP完全问题12.2.1 NP完全问题的定义一、完全问
11、题的定义1、难题定义12.6 令是一个判定问题，如果对中的每一个问题，有，就说判定问题是一个难题。2、完全问题定义12.7 令是一个判定问题，如果：(1) ，并且：(2) 对中的所有问题，都有；则称判定问题是完全的。3、难题和完全问题的差别是完全问题，是难题，则必定在类中，而不一定在类中。二、完全问题的证明1、归约的传递性定理12.3 令、和是三个判定问题，满足，及，则有。证明 假定问题的实例由个符号组成。因为，存在确定性算法，以用多项式时间，把问题的实例转换为问题的实例。使得的答案为，当且仅当的答案是。若算法每一步最多可输出个符号，则算法的输出规模，不会超过个符号。它们组成了问题的实例。因为
12、，存在确定性算法，以多项式的时间，把问题的实例，转换为问题的实例，使得的答案是，当且仅当的答案是。令算法是把算法和算法合并起来的算法，则算法也是一个确定性的算法，并且以多项式时间，把问题的实例转换为问题的实例，并且使得的答案为，当且仅当的答案是。由此得出，以多项式时间归约于，即。2、完全问题的特性定理12.4 令和是中的两个问题，使得。如果是完全的，则也是完全的。证明 因为是完全的，令是中任意一个问题，则有；因为，根据定理12.3，有。因为，并且在中是任意的，根据定义12.7，是完全的。3、完全问题的证明：证明下面两件事情：(1) ，并且： (2) 存在一个完全问题，使得；例12.4 已知哈密
13、尔顿回路问题HAMILTONIAN CYCLE是一个完全问题，证明货郎担问题TRAVELING SALESMAN也是一个完全问题。哈密尔顿回路问题：给定无向图，是否存在一条回路，使得图中每个顶点在回路中出现一次且仅一次。货郎担问题：给定个城市和最短距离，是否存在从某个城市出发、经过每个城市一次且仅一次、最后回到出发城市、且距离小于或等于的路线。1）证明货郎担问题是问题。例12.2中已经说明。2）证明哈密尔顿回路问题可用多项式时间归约为货郎担问题，即HAMILTONIAN CYCLE TRAVELING SALESMAN令是HAMILTONIAN CYCLE问题的任一实例，。构造赋权图，使得，。
14、对中的每一条边赋予如下的长度：（12.2.1）令。可以由一个算法在多项式时间里完成这个构造。因此，哈密尔顿回路问题可以用多项式时间归约为货郎担问题。3）证明中包含一条哈密尔顿回路，当且仅当中存在一条经过各个顶点一次，且全长不超过的路径。(1) 中包含一条哈密尔顿回路，设这条回路是。则该回路也是中一条经过各个顶点一次且仅一次的回路，根据式（12.2.1），这条回路长度为，因此，这条路径满足货郎担问题。(2) 中存在一条满足货郎担问题的路径，则这条路径经过中各个顶点一次且仅一次，最后回到起始出发顶点的回路，因此它是一条哈密尔顿回路。综上所述，关系HAMILTONIAN CYCLE TRAVELIN
15、G SALESMAN成立。所以TRAVELING SALESMAN问题也是一个完全问题。12.2.2 几个典型的NP完全问题12.3.2.1 可满足性问题（SATISFIABILITY）一、可满足性问题1、合取范式：由若干个析取子句的合取构成的布尔表达式。例：2、合取范式的可满足性：对合取范式的相应布尔变量赋值，使的真值为真，就说布尔表达式是可满足的。例：上式中，只要使、和为真，则表达式为真。因此，这个式子是可满足的。3、可满足性问题：判定问题：SATISFIABILITY输入：CNF布尔表达式f问题：对布尔表达式f中的布尔变量赋值,是否可使f的真值为真二、可满足性问题是完全的定理12.5（C
