第10章_NP完全问题.ppt

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

1、1第10章NP完全问题210.1引言10.2P类10.3NP类10.4NP完全问题10.5co-NP类(略)10.6NPI类(略)10.7四种类之间的关系(略)10.x近似算法初步310.1引言在前面的各章中，我们对一些算法的设计和分析进行了讨论，这些算法的运行时间可用低次多项式来表示。在这一章，我们将注意力集中在这样一类问题，这些问题至今没有找到有效算法，而且今后也有可能证明它们不存在有效算法。设П是任意问题，如果对该问题存在一个算法，它的时间复杂性是O(nk)，其中n是输入大小、k是非负整数，

2、我们说问题П存在多项式时间算法。现实世界的许多问题并不属于这个范畴，因为求解这些问题耗费的时间需用指数函数或阶乘函数来表示。4⑴易求解问题存在多项式时间算法。⑵难解问题到目前为止不存在多项式时间算法。本章将研究难解问题的一个子类，通常称为NP完全问题(NPC问题)。这一类问题目前约有3000多个，其中还包括数百个著名问题。它们有一个共同特性，如果它们中的一个是多项式可解的话，那么所有其它问题也是多项式可解的。现存的求解这些问题算法的运行时间，对于中等大小的输入也要用几百或几千年的时间。5⑶判定问题

3、为了研究问题的复杂性，我们必须将问题抽象。为了简化问题，我们只考虑一类简单的问题，称为“判定性问题”。也就是说提出一个问题，只需要回答Yes或者No。任何一般的最优化问题都可以转化为一系列判定性问题。例如，求图中从结点A到结点B的最短路径。该问题可以转化成如下形式：从A到B是否有长度为1的最短路径？No从A到B是否有长度为2的最短路径？No………………………………………？No从A到B是否有长度为k-1的最短路径？No从A到B是否有长度为k的最短路径？Yes如果问到了k的时候，回答了Yes，则停止发

4、问。我们可以说，从结点A到结点B的最短路径长度为k。610.2P类⑴确定性算法定义10.1(Page176)设A是求解问题П的一个算法。如果在展示问题П的一个实例时，在整个执行过程中每一步都只有一种选择，则称A是确定性算法。因此对于同样的输入，实例一遍又一遍地执行，它的输出从不改变。在前面各章所讨论的所有算法都是确定性的。给出一个无向图G=(V,E)，它有哈密顿回路吗？即在图中是否存在一条恰好访问每个结点一次的回路。可以用穷举法来求解，一条回路一条回路检查下去，最终便能得到结果。但是穷举法的算法时

5、间复杂性是指数级的，计算时间随问题规模成指数型增长，问题很快就变得不可计算了，所以确定性算法对此类问题无效。7⑵P类定义定义10.2(Page176)判定问题的P类由这样的判定问题组成，它们的Yes/No解可以用确定性算法在运行多项式步数内，例如在O(nk)步内得到，其中k是某个非负整数，n是输入大小。例1：给出一个有n个整数的表，它们是否按降序排列？答：只要检查表中相邻二个数即可，运行时间为O(n)。例2：给出二个整数集合，它们的交集是否为空？答：先将所有整数排序，然后检查相邻二数是否相等，显然

6、运行时间为O(nlog2n)。810.3NP类有些计算问题是确定性的，例如“加减乘除”，你只要按照公式推导，按部就班一步步进行，就可以得到结果。但是，有些问题无法按部就班直接进行计算的。例如“找大质数”问题，已知目前最大质数，那么下一个大质数应该是多少呢？有没有一个公式可以一步步推算出来，显然这样的公式是没有的。这种问题的答案，是无法直接计算得到的，只能通过“猜算”来得到结果，这就是非确定性问题。这些问题通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的还是错误的。这个

7、可以告诉你“猜算”的答案正确与否的算法，称为非确定性算法。假如“猜算”可以在多项式时间内得到，那么该问题称作“多项式非确定性问题”。9⑴非确定性算法对于输入x，一个非确定性算法由猜测和验证二个阶段组成。⑴猜测阶段在这个阶段产生一个任意字符串y，它可能对应输入实例的一个解，也可以不对应解。事实上，它甚至可能不是所求解的合适形式，它可能在非确定算法的不同次运行中不同。它仅要求在多项式步数内产生这个串，即在O(ni)时间内，这里n=

8、x

9、，i是非负整数。对于许多问题，这一阶段可以在线性时间内完成。⑵验证

10、阶段首先检查产生的解串y是否有合适的形式，如果不是，则算法停下来并回答No；如果y是合适形式，那么算法继续检查它是否是问题实例x的解。若是，则算法停下来并回答Yes；否则算法停下来并回答No。我们也要求这个阶段在多项式步数内完成，即在O(nj)时间内，这里j是一个非负整数。非确定性算法的运行时间是由猜测阶段和验证阶段二部分耗费时间组成，因此它是O(nk)=O(ni)+O(nj)，k是某个非负整数。10例：求大整数n的一个真因数(即1和n本身以外的一个因数，并且该因数是素数)。这是一