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

算法设计与分析清华大学出版社第2章NP完全理论2.1下界2.2算法的极限2.3P类问题和NP类问题2.4NP完全问题2.5实验项目——SAT问题算法设计与分析清华大学出版社2.1下界对于任何待求解的问题，如果能找到一个尽可能大的函数g(n)（n为问题规模），使得求解该问题的所有算法都可以在Ω(g(n))的时间内完成，则函数g(n)称为该问题计算复杂性的下界（LowerBound）。如果已经知道一个和下界的效率类型相同的算法，则称该下界是紧密（Close）的。意义：评价算法；改进算法。算法设计与分析清华大学出版社对问题的输入中必须要处理的元素进行计数，同时，对必须要输出的元素进行计数。这种计数方法产生的是一个平凡下界（OrdinaryLowerBound）.2.1.1平凡下界例：生成n个元素的所有排列对象的算法属于Ω(n!)平凡下界往往过小而失去意义。例：TSP问题的平凡下界是Ω(n2)算法设计与分析清华大学出版社2.1.2判定树模型判定树（DecisionTrees）是这样一棵二叉树：它的每一个内部结点对应一个形如x≤y的比较，如果关系成立，则控制转移到该结点的左子树，否则，控制转移到该结点的右子树，它的每一个叶子结点表示问题的一个结果。在用判定树模型建立问题的时间下界时，通常忽略求解问题的所有算术运算，只考虑分支执行时的转移次数。算法设计与分析清华大学出版社a1a2a1a2a3是是是否否否a1a3a2a3a2a1a3a2a3a3a2a1a2a3a1a1a3a3a1a2a1a3a2否否是是例：对三个数进行排序的判定树算法设计与分析清华大学出版社2.1.3最优算法所谓最优算法（OptimalityAlgorithm）是指在某一种度量标准下，优于该问题的所有（可能的）算法。如果能够证明求解问题Π的任何算法的运行时间下界是Ω(g(n))，那么，对以时间O(g(n))来求解问题Π的任何算法，都认为是最优算法。算法设计与分析清华大学出版社2.2算法的极限2.2.1易解问题与难解问题2.2.2实际问题难以求解的原因2.2.3不可解问题算法设计与分析清华大学出版社2.2.1易解问题与难解问题通常将存在多项式时间算法的问题看作是易解问题（EasyProblem），将需要指数时间算法解决的问题看作是难解问题（HardProblem）。例：易解问题——排序问题、查找问题、欧拉回路难解问题——TSP问题、Hanio问题、Hamilton回路算法设计与分析清华大学出版社为什么把多项式时间复杂性作为易解问题和难解问题的分界线？1．多项式函数与指数函数的增长率有本质的差别2．计算机性能的提高对多项式时间算法和指数时间算法的影响不同3．多项式时间复杂性忽略了系数，但不影响易解问题和难解问题的划分4．多项式时间复杂性的闭包性5．多项式时间复杂性的独立性算法设计与分析清华大学出版社2.2.3不可解问题不能用计算机求解（不论耗费多少时间）的问题称为不可解问题（UnsolubleProblem）。例：不可解问题——停机问题、病毒检测作业：证明停机问题是不可解问题。算法设计与分析清华大学出版社2.3P类问题和NP类问题2.3.1判定问题2.3.2确定性算法与P类问题2.3.3非确定性算法与NP类问题算法设计与分析清华大学出版社2.3.1判定问题一个判定问题（DecisionProblem）是仅仅要求回答“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是求解问题Π的一个算法，如果算法A以如下猜测并验证的方式工作，就称算法A是非确定性（Nondeterminism）算法：（1）猜测阶段：在这个阶段，对问题的输入实例产生一个任意字符串y，在算法的每一次运行时，串y的值可能不同，因此，猜测以一种非确定的形式工作。（2）验证阶段：在这个阶段，用一个确定性算法验证：①检查在猜测阶段产生的串y是否是合适的形式，如果不是，则算法停下来并得到no；②如果串y是合适的形式，则验证它是否是问题的解，如果是，则算法停下来并得到yes，否则算法停下来并得到no。算法设计与分析清华大学出版社定义2.4如果对于某个判定问题Π，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个非确定性算法，得到yes或no的答案，则该判定问题Π是一个NP类（NondeterministicPolynomial）问题。关键——存在一个确定性算法，能够以多项式时间来检查和验证猜测阶段所产生的答案。例：NP类问题——Hamilton问题汉诺塔问题不是NP类问题算法设计与分析清华大学出版社P类问题和NP类问题的主要差别：P类问题可以用多项式时间的确定性算法来进行判定或求解；NP类问题可以用多项式时间的非确定性算法来进行判定或求解。算法设计与分析清华大学出版社2.4NP完全问题2.4.1问题变换与计算复杂性归约2.4.2NP完全问题的定义2.4.3基本的NP完全问题2.4.4NP完全问题的计算机处理算法设计与分析清华大学出版社2.4.1问题变换与计算复杂性归约定义2.5假设问题Π'存在一个算法A，对于问题Π'的输入实例I'，算法A求解问题Π'得到一个输出O'，另外一个问题Π的输入实例是I，对应于输入I，问题Π有一个输出O，则问题Π变换到问题Π'是一个三步的过程：1.输入转换：把问题Π的输入I转换为问题Π'的适当输入I'；2.问题求解：对问题Π'应用算法A产生一个输出O'；3.输出转换：把问题Π'的输出O'转换为问题Π对应于输入I的正确输出。算法设计与分析清华大学出版社问题变换的一般过程问题Π问题Π'算法AI输入转换I'O'O输出转换问题变换的主要目的不是给出解决一个问题的算法，而是给出通过另一个问题理解一个问题的计算时间上下限的一种方式。算法设计与分析清华大学出版社排序问题——输入I'是一组整数X=(x1,x2,…,xn)，输出O'是这组整数的一个排列xi1≤xi2≤…≤xin。配对问题——输入I是两组整数X=(x1,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'转化为配对问题的输出O，这可以通过配对每组整数的第一个元素、第二个元素、……来得到。配对问题到排序问题的变换过程算法设计与分析清华大学出版社定理2.3（计算时间下限归约）若已知问题Π的计算时间下限是T(n)，且问题Π可τ(n)变换到问题Π'，即Π∝τ(n)Π'，则T(n)－O(τ(n))为问题Π'的一个计算时间下限。定理2.4（计算时间上限归约）若已知问题Π'的计算时间上限是T(n)，且问题Π可τ(n)变换到问题Π'，即Π∝τ(n)Π'，则T(n)＋O(τ(n))为问题Π的一个计算时间上限。计算时间下限归约：T(n)τ(n)T(n)－O(τ(n))计算时间上限归约：T(n)＋O(τ(n))τ(n)T(n)问题Π变换问题Π'算法设计与分析清华大学出版社定理2.5设Π、Π'和Π''是三个判定问题，若Π∝pΠ'且Π'∝pΠ''，则Π∝pΠ''。多项式时间复杂性具有闭包性。算法设计与分析清华大学出版社2.4.2NP完全问题的定义定义2.6令Π是一个判定问题，如果问题Π属于NP类问题，并且对NP类问题中的每一个问题Π'，都有Π'∝pΠ，则称判定问题Π是一个NP完全问题（NPCompleteProblem），有时把NP完全问题记为NPC。NP类问题NP完全问题算法设计与分析清华大学出版社P＝NP？广义上说，P类问题是可以用确定性算法在多项式时间内求解的一类问题，NP类问题是可以用非确定性算法在多项式时间猜测并验证的一类问题，而且P⊆NP。目前人们猜测P≠NP，则P类问题、NP类问题、NP完全问题之间的关系如下：NP类问题P类问题NPC问题算法设计与分析清华大学出版社定义2.7令Π是一个判定问题，如果对于NP类问题中的每一个问题Π'，都有Π'∝pΠ，则称判定问题Π是一个NP难问题。NP类问题NP难问题算法设计与分析清华大学出版社如果Π是NP完全问题，Π’是NP难问题，那么，他们之间的差别在于Π必定是NP类问题，而Π’不一定在NP类问题中。一般而言，若判定问题属于NP完全问题，则相应的最优化问题属于NP难问题。NP完全问题和NP难问题的区别：算法设计与分析清华大学出版社2.4.3基本的NP完全问题证明一个判定问题Π是NP完全问题需要经过两步：（1）证明问题Π属于NP类问题，也就是说，可以在多项式时间以确定性算法验证一个任意生成的串，以确定它是不是问题的一个解；（2）证明NP类问题中的每一个问题都能在多项式时间变换为问题Π。由于多项式问题变换具有传递性，所以，只需证明一个已知的NP完全问题能够在多项式时间变换为问题Π。算法设计与分析清华大学出版社NP完全问题的证明思想NP类问题已知的NP完全问题要证明的NP完全问题算法设计与分析清华大学出版社一些基本的NP完全问题：1．SAT问题（BooleanSatisfiabilityProblem）2．最大团问题（MaximumCliqueProblem）3．图着色问题（GraphColoringProblem）4.哈密顿回路问题（HamiltonianCycleProblem）5．TSP问题（TravelingSalsmanProblem）6．顶点覆盖问题（VertexCoverProblem）7．最长路径问题（LongestPathProblem）8．子集和问题（SumofSubsetProblem）算法设计与分析清华大学出版社2.4.4NP完全问题的计算机处理1．采用先进的算法设计技术2．充分利用限制条件3．近似算法4．概率算法5．并行计算6．智能算法算法设计与分析清华大学出版社2.5实验项目——SAT问题1.实验题目SAT问题也称为合取范式的可满足问题，一个合取范式形如：A1∧A2∧…∧An，子句Ai（1≤i≤n）形如：a1∨a2∨…∨ak，其中，ai称为文字，为某一布尔变量或该布尔变量的非。SAT问题是指：是否存在一组对所有布尔变量的赋值（TRUE或FALSE），使得整个合取范式取值为真。算法设计与分析清华大学出版社2.实验目的（1）掌握NP完全问题的特点；（2）理解这样一个观点：NP完全问题的算法具有指数时间，而指数时间算法的计算时间随着问题规模的增长而快速增长。3.实验要求（1）设计算法求解SAT问题；（2）设定问题规模为3、5、10、20、50，设计实验程序考察算法的时间性能。