程序设计技术NP完全性.pptVIP

* 一些基本的NP完全问题： 1．SAT问题（Boolean Satisfiability Problem） 2．最大团问题（Maximum Clique Problem） 3．图着色问题（Graph Coloring Problem） 4. 哈密顿回路问题（Hamiltonian Cycle Problem） 5．TSP问题（Traveling Salsman Problem） 6．顶点覆盖问题（Vertex Cover Problem） 7．最长路径问题（Longest Path Problem） 8．子集和问题（Sum of Subset Problem） * NP完全问题的计算机处理 1．采用先进的算法设计技术 2．充分利用限制条件 3．近似算法 4．概率算法 5．并行计算 6．智能算法 * 程序设计技术 第九章 NP-完全性 * 提要 下界 算法的极限 P类问题和NP类问题 NP完全问题 * 下界 对于任何待求解的问题，如果能找到一个尽可能大的函数g(n)（n为问题规模），使得求解该问题的所有算法都可以在Ω(g(n))的时间内完成，则函数g(n)称为该问题计算复杂性的下界（Lower Bound）。 如果已经知道一个和下界的效率类型相同的算法，则称该下界是紧密（Close）的。 意义：评价算法；改进算法。 * 对问题的输入中必须要处理的元素进行计数，同时，对必须要输出的元素进行计数。这种计数方法产生的是一个平凡下界（Ordinary Lower Bound）. 平凡下界 例 ：生成 n 个元素的所有排列对象的算法属于Ω(n!) 平凡下界往往过小而失去意义。 例：TSP问题的平凡下界是Ω(n2) * 判定树模型 判定树（Decision Trees）是这样一棵二叉树：它的每一个内部结点对应一个形如x≤y的比较，如果关系成立，则控制转移到该结点的左子树，否则，控制转移到该结点的右子树，它的每一个叶子结点表示问题的一个结果。 在用判定树模型建立问题的时间下界时，通常忽略求解问题的所有算术运算，只考虑分支执行时的转移次数。 * a1a2 a1a2a3 是 是 是 否 否 否 a1a3 a2a3 a2a1a3 a2a3 a3a2a1 a2a3a1 a1a3 a3a1a2 a1a3a2 否 否 是 是 例：对三个数进行排序的判定树 * 最优算法 所谓最优算法（Optimality Algorithm）是指在某一种度量标准下，优于该问题的所有（可能的）算法。 如果能够证明求解问题Π的任何算法的运行时间下界是Ω(g(n))，那么，对以时间O(g(n))来求解问题Π的任何算法，都认为是最优算法。 * 算法的极限 易解问题与难解问题 实际问题难以求解的原因 不可解问题 * 易解问题与难解问题 通常将存在多项式时间算法的问题看作是易解问题（Easy Problem），将需要指数时间算法解决的问题看作是难解问题（Hard Problem）。 例：易解问题——排序问题、查找问题、欧拉回路 难解问题——TSP问题、 Hanio问题、Hamilton回路 * 为什么把多项式时间复杂性作为易解问题和难解问题的分界线？ 1．多项式函数与指数函数的增长率有本质的差别 2．计算机性能的提高对多项式时间算法和指数时间算法的影响不同 3．多项式时间复杂性忽略了系数，但不影响易解问题和难解问题的划分 4．多项式时间复杂性的闭包性 5．多项式时间复杂性的独立性 * 不可解问题 不能用计算机求解（不论耗费多少时间）的问题称为不可解问题（Unsoluble Problem）。 例：不可解问题——停机问题 (判断一个程序是否会在有限的时间之内结束运行的问题。这个问题是由图灵提出的一个不可解问题，即无法在有限的时间内得到解的问题。) * P类问题和NP类问题 判定问题 确定性算法与P类问题 非确定性算法与NP类问题 * 判定问题 一个判定问题（Decision Problem）是仅仅要求回答“yes”或“no”的问题。 判定问题的重要特性——证比求易 判定问题→语言的识别问题→计算模型 * 确定性算法与P类问题 定义1 设A是求解问题Π的一个算法，如果在算法的整个执行过程中，每一步只有一个确定的选择，则称算法A是确定性（Determinism）算法。 定义2 如果对于某个判定问题Π，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个确定性算法，得到yes或no的答案，则该判定问题Π是一个 P 类（Polynomial）问题。 所有