第2章NP完全理论.ppt.ppt

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，设计实验程序考察算法的时间性能。 算法设计与分析 数计学院 第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 Bound）. 2.1.1 平凡下界 例 ：生成 n 个元素的所有排列对象的算法属于Ω(n!) 平凡下界往往过小而失去意义。 例：TSP问题的平凡下界是Ω(n2) 2.1.2 判定树模型 判定树（Decision Trees）是这样一棵二叉树：它的每一个内部结点对应一个形如x≤y的比较，如果关系成立，则控制转移到该结点的左子树，否则，控制转移到该结点的右子树，它的每一个叶子结点表示问题的一个结果。 在用判定树模型建立问题的时间下界时，通常忽略求解问题的所有算术运算，只考虑分支执行时的转移次数。 a1a2 a1a2a3 是 是 是 否 否 否 a1a3 a2a3 a2a1a3 a2a3 a3a2a1 a2a3a1 a1a3 a3a1a2 a1a3a2 否 否 是 是 例：对三个数进行排序的判定树 2.1.3 最优算法 所谓最优算法（Optimality Algorithm）是指在某一种度量标准下，优于该问题的所有（可能的）算法。 如果能够证明求解问题Π的任何算法的运行时间下界是Ω(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回路 为什么把多项式时间复杂性作为易解问题和难解问题的分界线？ 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 Problem）是仅仅要求回答“yes”或“no”的问题。 判定问题的重要特性——证比求易 判定问题→语言的识别问题→计算模型 2.3.2 确定性算法与P类问题 定义2.1 设A是求解问题Π的一个算法，如果在算法的整个执行过程中，每一步只有一个确定的选择，则称算法A是确定性（Determinism）算法。 定义2.2 如果对于某个判定问题Π，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个确定性算法，