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

《算法设计与分析_王红梅_第2章 NP完全理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第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）的。意义：评价算法；改进算法。对问题的输入中必须要处理的元素进行计数，同时，对必须要输出的元素进行计数。这种计数方法产生的是一个平凡下界（Ordin

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

3、

4、作是易解问题（EasyProblem），将需要指数时间算法解决的问题看作是难解问题（HardProblem）。例：易解问题——排序问题、查找问题、欧拉回路难解问题——TSP问题、Hanio问题、Hamilton回路为什么把多项式时间复杂性作为易解问题和难解问题的分界线？1．多项式函数与指数函数的增长率有本质的差别2．计算机性能的提高对多项式时间算法和指数时间算法的影响不同3．多项式时间复杂性忽略了系数，但不影响易解问题和难解问题的划分4．多项式时间复杂性的闭包性5．多项式时间复杂性的独立性2.2.3不可解问题不能用计算机求解（不论耗费多少时间）

5、的问题称为不可解问题（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是确定性（De

6、terminism）算法。定义2.2如果对于某个判定问题Π，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个确定性算法，得到yes或no的答案，则该判定问题Π是一个P类（Polynomial）问题。所有易解问题都是P类问题2.3.3非确定性算法与NP类问题定义2.3设A是求解问题Π的一个算法，如果算法A以如下猜测并验证的方式工作，就称算法A是非确定性（Nondeterminism）算法：（1）猜测阶段：在这个阶段，对问题的输入实例产生一个任意字符串y，在算法的每一次运行时，串y的值可能不同，因此，猜测以一种非确定的形式

7、工作。（2）验证阶段：在这个阶段，用一个确定性算法验证：①检查在猜测阶段产生的串y是否是合适的形式，如果不是，则算法停下来并得到no；②如果串y是合适的形式，则验证它是否是问题的解，如果是，则算法停下来并得到yes，否则算法停下来并得到no。定义2.4如果对于某个判定问题Π，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个非确定性算法，得到yes或no的答案，则该判定问题Π是一个NP类（NondeterministicPolynomial）问题。关键——存在一个确定性算法，能够以多项式时间来检查和验证猜测阶段所产生的答

8、案。例：NP类问题——Hamilton问题汉诺塔问题不是NP类问题P类问题和NP类问题的主要差别：P类问题可以用多项式时间的确定性算法来进行判定或求解