第10来章n完全问题.pptVIP

* 第10章 NP完全问题 * 10.1 引言 10.2 P类 10.3 NP类 10.4 NP完全问题 10.5 co-NP类(略) 10.6 NPI类(略) 10.7 四种类之间的关系(略) 10.x 近似算法初步 * 10.1 引言 在前面的各章中，我们对一些算法的设计和分析进行了讨论，这些算法的运行时间可用低次多项式来表示。在这一章，我们将注意力集中在这样一类问题，这些问题至今没有找到有效算法，而且今后也有可能证明它们不存在有效算法。 设П是任意问题，如果对该问题存在一个算法，它的时间复杂性是O(nk)，其中n是输入大小、k是非负整数，我们说问题П存在多项式时间算法。现实世界的许多问题并不属于这个范畴，因为求解这些问题耗费的时间需用指数函数或阶乘函数来表示。 * ⑴易求解问题 存在多项式时间算法。 ⑵难解问题 到目前为止不存在多项式时间算法。 本章将研究难解问题的一个子类，通常称为NP完全问题(NPC问题)。这一类问题目前约有3000多个，其中还包括数百个著名问题。它们有一个共同特性，如果它们中的一个是多项式可解的话，那么所有其它问题也是多项式可解的。现存的求解这些问题算法的运行时间，对于中等大小的输入也要用几百或几千年的时间。 * ⑶判定问题 为了研究问题的复杂性，我们必须将问题抽象。为了简化问题，我们只考虑一类简单的问题，称为“判定性问题”。也就是说提出一个问题，只需要回答Yes或者No。任何一般的最优化问题都可以转化为一系列判定性问题。 例如，求图中从结点A到结点B的最短路径。该问题可以转化成如下形式： 从A到B是否有长度为1的最短路径？ No 从A到B是否有长度为2的最短路径？ No ………………………………………？ No 从A到B是否有长度为k-1的最短路径？ No 从A到B是否有长度为k的最短路径？ Yes 如果问到了k的时候，回答了Yes，则停止发问。我们可以说，从结点A到结点B的最短路径长度为k。 * 10.2 P类 ⑴确定性算法 定义10.1(Page 176) 设A是求解问题П的一个算法。如果在展示问题П的一个实例时，在整个执行过程中每一步都只有一种选择，则称A是确定性算法。因此对于同样的输入，实例一遍又一遍地执行，它的输出从不改变。 在前面各章所讨论的所有算法都是确定性的。给出一个无向图G=(V,E)，它有哈密顿回路吗？即在图中是否存在一条恰好访问每个结点一次的回路。 可以用穷举法来求解，一条回路一条回路检查下去，最终便能得到结果。但是穷举法的算法时间复杂性是指数级的，计算时间随问题规模成指数型增长，问题很快就变得不可计算了，所以确定性算法对此类问题无效。 * ⑵P类定义 定义10.2(Page 176) 判定问题的P类由这样的判定问题组成，它们的Yes/No解可以用确定性算法在运行多项式步数内，例如在O(nk)步内得到，其中k是某个非负整数，n是输入大小。 例1：给出一个有n个整数的表，它们是否按降序排列？ 答：只要检查表中相邻二个数即可，运行时间为O(n)。 例2：给出二个整数集合，它们的交集是否为空？ 答：先将所有整数排序，然后检查相邻二数是否相等，显然运行时间为 O(nlog2n)。 * 10.3 NP类 有些计算问题是确定性的，例如“加减乘除”，你只要按照公式推导，按部就班一步步进行，就可以得到结果。但是，有些问题无法按部就班直接进行计算的。例如 “找大质数” 问题，已知目前最大质数，那么下一个大质数应该是多少呢？有没有一个公式可以一步步推算出来，显然这样的公式是没有的。 这种问题的答案，是无法直接计算得到的，只能通过“猜算”来得到结果，这就是非确定性问题。这些问题通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，称为非确定性算法。假如“猜算”可以在多项式时间内得到，那么该问题称作“多项式非确定性问题”。 * ⑴非确定性算法 对于输入x，一个非确定性算法由猜测和验证二个阶段组成。 ⑴猜测阶段 在这个阶段产生一个任意字符串y，它可能对应输入实例的一个解，也可以不对应解。事实上，它甚至可能不是所求解的合适形式，它可能在非确定算法的不同次运行中不同。它仅要求在多项式步数内产生这个串，即在O(ni)时间内，这里n=|x|，i是非负整数。对于许多问题，这一阶段可以在线性时间内完成。 ⑵验证阶段 首先检查产生的解串y是否有合适的形式，如果不是，则算法停下来并回答No；如果y是合适形式，那么算法继续检查它是否是问题实例x的解。若是，则算法停下来并回答Y