算法设计与分析王红梅第2章NP完全理论.ppt

《算法设计与分析王红梅第2章NP完全理论.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析王红梅第2章NP完全理论.ppt（33页珍藏版）》请在三一办公上搜索。

1、第2章 NP完全理论,2.1 下界,2.2 算法的极限,2.3 P类问题和NP类问题,2.4 NP完全问题,2.5 实验项目SAT问题,2.1 下界,对于任何待求解的问题，如果能找到一个尽可能大的函数g(n)（n为问题规模），使得求解该问题的所有算法都可以在(g(n)的时间内完成，则函数g(n)称为该问题计算复杂性的下界（Lower Bound）。如果已经知道一个和下界的效率类型相同的算法，则称该下界是紧密（Close）的。意义：评价算法；改进算法。,对问题的输入中必须要处理的元素进行计数，同时，对必须要输出的元素进行计数。这种计数方法产生的是一个平凡下界（Ordinary Lower Bou

2、nd）.,2.1.1 平凡下界,例：生成 n 个元素的所有排列对象的算法属于(n!),平凡下界往往过小而失去意义。例：TSP问题的平凡下界是(n2),2.1.2 判定树模型,判定树（Decision Trees）是这样一棵二叉树：它的每一个内部结点对应一个形如xy的比较，如果关系成立，则控制转移到该结点的左子树，否则，控制转移到该结点的右子树，它的每一个叶子结点表示问题的一个结果。在用判定树模型建立问题的时间下界时，通常忽略求解问题的所有算术运算，只考虑分支执行时的转移次数。,例：对三个数进行排序的判定树,2.1.3 最优算法,所谓最优算法（Optimality Algorithm）是指在某一

3、种度量标准下，优于该问题的所有（可能的）算法。如果能够证明求解问题的任何算法的运行时间下界是(g(n)，那么，对以时间O(g(n)来求解问题的任何算法，都认为是最优算法。,2.2 算法的极限,2.2.1 易解问题与难解问题,2.2.2 实际问题难以求解的原因,2.2.3 不可解问题,2.2.1 易解问题与难解问题,通常将存在多项式时间算法的问题看作是易解问题（Easy Problem），将需要指数时间算法解决的问题看作是难解问题（Hard Problem）。例：易解问题排序问题、查找问题、欧拉回路 难解问题TSP问题、Hanio问题、Hamilton回路,为什么把多项式时间复杂性作为易解问题和

4、难解问题的分界线？,1多项式函数与指数函数的增长率有本质的差别2计算机性能的提高对多项式时间算法和指数时间算法的影响不同3多项式时间复杂性忽略了系数，但不影响易解问题和难解问题的划分4多项式时间复杂性的闭包性5多项式时间复杂性的独立性,2.2.3 不可解问题,不能用计算机求解（不论耗费多少时间）的问题称为不可解问题（Unsoluble Problem）。,例：不可解问题停机问题、病毒检测作业：证明停机问题是不可解问题。,2.3 P类问题和NP类问题,2.3.1 判定问题,2.3.2 确定性算法与P类问题,2.3.3 非确定性算法与NP类问题,2.3.1 判定问题,一个判定问题（Decision

5、 Problem）是仅仅要求回答“yes”或“no”的问题。,判定问题的重要特性证比求易,判定问题语言的识别问题计算模型,2.3.2 确定性算法与P类问题,定义2.1 设A是求解问题的一个算法，如果在算法的整个执行过程中，每一步只有一个确定的选择，则称算法A是确定性（Determinism）算法。定义2.2 如果对于某个判定问题，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个确定性算法，得到yes或no的答案，则该判定问题是一个 P 类（Polynomial）问题。,所有易解问题都是P类问题,2.3.3 非确定性算法与NP类问题,定义2.3 设A是求解问题的一个算法

6、，如果算法A以如下猜测并验证的方式工作，就称算法A是非确定性（Nondeterminism）算法：（1）猜测阶段：在这个阶段，对问题的输入实例产生一个任意字符串y，在算法的每一次运行时，串y的值可能不同，因此，猜测以一种非确定的形式工作。（2）验证阶段：在这个阶段，用一个确定性算法验证：检查在猜测阶段产生的串y是否是合适的形式，如果不是，则算法停下来并得到no；如果串y是合适的形式，则验证它是否是问题的解，如果是，则算法停下来并得到yes，否则算法停下来并得到no。,定义2.4 如果对于某个判定问题，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个非确定性算法，得到y

7、es或no的答案，则该判定问题是一个 NP 类（Nondeterministic Polynomial）问题。,关键存在一个确定性算法，能够以多项式时间来检查和验证猜测阶段所产生的答案。例：NP类问题Hamilton问题 汉诺塔问题不是NP类问题,P类问题和NP类问题的主要差别：,P类问题可以用多项式时间的确定性算法来进行判定或求解；NP类问题可以用多项式时间的非确定性算法来进行判定或求解。,2.4 NP完全问题,2.4.1 问题变换与计算复杂性归约,2.4.2 NP完全问题的定义,2.4.3 基本的NP完全问题,2.4.4 NP完全问题的计算机处理,2.4.1 问题变换与计算复杂性归约,定义

8、 2.5 假设问题存在一个算法A，对于问题的输入实例I，算法A求解问题得到一个输出O，另外一个问题的输入实例是I，对应于输入I，问题有一个输出O，则问题变换到问题是一个三步的过程：1.输入转换：把问题的输入I转换为问题的适当输入I；2.问题求解：对问题应用算法A产生一个输出O；3.输出转换：把问题的输出O转换为问题对应于输入I的正确输出。,问题变换的一般过程,问题变换的主要目的不是给出解决一个问题的算法，而是给出通过另一个问题理解一个问题的计算时间上下限的一种方式。,排序问题输入I是一组整数X=(x1,x2,xn)，输出O是这组整数的一个排列xi1xi2xin。配对问题输入I是两组整数X=(x

9、1,x2,xn)和Y=(y1,y2,yn)，输出O是两组整数的元素配对，即X中的最小值与Y中的最小值配对，X中的次小值与Y中的次小值配对，依此类推。,例：配对问题到排序问题的变换,配对问题到排序问题的变换有助于建立配对问题代价的一个上限，因为上述输入和输出转换都是在多项式时间完成，所以，如果排序问题有多项式时间算法，则配对问题也一定有多项式时间算法。,假设存在算法A解决排序问题，则配对问题可以变换到排序问题：1把配对问题的输入I转化为排序问题的两个输入I1和I2；2排序这两组整数，即应用算法A对两个输入I1和I2分别排序得到两个有序序列O1 和O2；3把排序问题的输出O1和O2转化为配对问题的

10、输出O，这可以通过配对每组整数的第一个元素、第二个元素、来得到。,配对问题到排序问题的变换过程,定理2.3（计算时间下限归约）若已知问题的计算时间下限是T(n)，且问题可(n)变换到问题，即(n)，则T(n)O(n)为问题的一个计算时间下限。,定理2.4（计算时间上限归约）若已知问题的计算时间上限是T(n)，且问题可(n)变换到问题，即(n)，则T(n)O(n)为问题的一个计算时间上限。,定理2.5 设、和是三个判定问题，若p且p，则p。,多项式时间复杂性具有闭包性。,2.4.2 NP完全问题的定义,定义2.6 令是一个判定问题，如果问题属于NP类问题，并且对NP类问题中的每一个问题，都有p，

11、则称判定问题是一个NP完全问题（NP Complete Problem），有时把NP完全问题记为NPC。,PNP？广义上说，P类问题是可以用确定性算法在多项式时间内求解的一类问题，NP类问题是可以用非确定性算法在多项式时间猜测并验证的一类问题，而且PNP。,目前人们猜测PNP，则P类问题、NP类问题、NP完全问题之间的关系如下：,定义2.7 令是一个判定问题，如果对于NP类问题中的每一个问题，都有p，则称判定问题是一个NP难问题。,如果是NP完全问题，是NP难问题，那么，他们之间的差别在于必定是NP类问题，而不一定在NP类问题中。一般而言，若判定问题属于NP完全问题，则相应的最优化问题属于NP

12、难问题。,NP完全问题和NP难问题的区别：,2.4.3 基本的NP完全问题,证明一个判定问题是NP完全问题需要经过两步：,（1）证明问题属于NP类问题，也就是说，可以在多项式时间以确定性算法验证一个任意生成的串，以确定它是不是问题的一个解；（2）证明NP类问题中的每一个问题都能在多项式时间变换为问题。由于多项式问题变换具有传递性，所以，只需证明一个已知的NP完全问题能够在多项式时间变换为问题。,NP完全问题的证明思想,一些基本的NP完全问题：,1SAT问题（Boolean Satisfiability Problem）2最大团问题（Maximum Clique Problem）3图着色问题（G

13、raph Coloring Problem）4.哈密顿回路问题（Hamiltonian Cycle Problem）5TSP问题（Traveling Salsman Problem）6顶点覆盖问题（Vertex Cover Problem）7最长路径问题（Longest Path Problem）8子集和问题（Sum of Subset Problem）,2.4.4 NP完全问题的计算机处理,1采用先进的算法设计技术2充分利用限制条件3近似算法4概率算法5并行计算6智能算法,2.5 实验项目SAT问题,1.实验题目 SAT问题也称为合取范式的可满足问题，一个合取范式形如：A1A2An，子句Ai（1in）形如：a1a2ak，其中，ai称为文字，为某一布尔变量或该布尔变量的非。SAT问题是指：是否存在一组对所有布尔变量的赋值（TRUE或FALSE），使得整个合取范式取值为真。,2.实验目的（1）掌握NP完全问题的特点；（2）理解这样一个观点：NP完全问题的算法具有指数时间，而指数时间算法的计算时间随着问题规模的增长而快速增长。,3.实验要求（1）设计算法求解SAT问题；（2）设定问题规模为3、5、10、20、50，设计实验程序考察算法的时间性能。,