10 NP-完全问题.ppt

10 NP-完全问题 学习要点 理解有限自动机、下推自动机和图灵机计算模型 理解P类与NP问题 了解NP-完全问题 思考NP-完全问题的计算机实现 计算模型 建立计算模型的目的是为了使问题的计算复杂性分析有一 个共同的客观尺度。 3个基本计算模型： （1）有限自动机 （2）下推自动机 （3）图灵机 有限自动机 有限自动机 下推自动机 下推自动机 下推自动机 图灵机 图灵机 图灵机 图灵机 图灵机 一些难解问题 一些难解问题 一些难解问题 一些难解问题 一些难解问题 一些难解问题 多项式界与P类问题 多项式界与P类问题 多项式界与P类问题 多项式界与P类问题 多项式界与P类问题 问题求解与判定问题 问题求解与判定问题 P类与NP类问题 一般地说，将可由多项式时间算法求解的问题看作是易处理的问题，而将需要超多项式时间才能求解的问题看作是难处理的问题。 有许多问题，至今人们还没有找到解决这些问题的多项式时间算法，也没有人能够证明这些问题需要超多项式时间下界。 在图灵机计算模型下，这类问题的计算复杂性至今未知。 为了研究这类问题的计算复杂性，人们提出了另一个能力更强的计算模型，即非确定性图灵机计算模型，简记为 NDTM(Nondeterministic Turing Machine)。 在非确定性图灵机计算模型下，许多问题可以在多项式时间内求解。 非确定性图灵机 P类与NP类语言 多项式时间验证 NP完全问题 P?NP。 直观上看，P类问题是确定性计算模型下的易解问题类，而NP类问题是非确定性计算模型下的易验证问题类。 大多数的计算机科学家认为NP类中包含了不属于P类的语言，即P≠NP。 可以证明，即如果一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内求解，即P=NP。 NP完全问题没有多项式时间算法。 多项式时间变换 多项式时间变换 Cook定理 一些典型的NP完全问题 NP完全问题的计算机实现 NP完全问题的近似算法 近似算法的性能 顶点覆盖问题的近似算法 顶点覆盖问题的近似算法 顶点覆盖问题的近似算法 旅行售货员问题近似算法 满足三角不等式的旅行售货员问题 一般的旅行售货员问题 集合覆盖问题的近似算法 集合覆盖问题的近似算法 集合覆盖问题的近似算法 子集和问题的近似算法 子集和问题的指数时间算法 子集和问题的完全多项式时间近似格式 子集和问题的完全多项式时间近似格式 定义：语言L是NP完全的当且仅当 (1)L∈NP； (2)对于所有L’∈NP 有 L’ ∝p L。 如果有一个语言L满足上述性质(2)，但不一定满足性质(1)，则称该语言是NP难的。所有NP完全语言构成的语言类称为NP完全 语言类，记为NPC。 设 ， 是2个语言。所谓语言 能在多项式时间内变换为语言 (简记为 ∝p )是指存在映身f: ，且f满足： (1)有一个计算f的多项式时间确定性图灵机； (2)对于所有x∈ ，x∈ ，当且仅当f(x)∈ 。 定理10-2：设L是NP完全的，则 (1)L∈P当且仅当P＝NP； (2)若L∝p ，且 ∈NP，则 是NP完全的。 定理的(2)可用来证明问题的NP完全性。但前提是：要有第一个NP完全问题L。 CooK定理： 布尔表达式的可满足性问题SAT是NP完全的。 部分NP完全问题树 迄今为止，所有的NP完全问题都还没有多项式时间算法。 对于这类问题，通常可采取以下几种解题策略。 (1)只对问题的特殊实例求解 (2)用动态规划法或分支限界法求解 (3)用概率算法求解 (4)只求近似解 (5)用启发式方法求解 迄今为止，所有的NP完全问题都还没有多项式时间算法。 对于这类问题，通常可采取以下几种解题策略。 (1)只对问题的特殊实例求解 (2)用动态规划法或分支限界法求解 (3)用概率算法求解 (4)只求近似解 (5)用启发式方法求解 若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c，则将该近似算法的性能比定义为?= 。在通常情况下，该性能比是问题输入规模n的一个函数ρ(n)，即 ≤ρ(n)。 该近似算法的相对误差定义为?= 。若对问题的输入规模n，有一函数ε(n)使得 ≤ε(n)，则称ε(n)为该近似算法的相对误差界。