第9章np完全性理论与近似算法

第9章np完全性理论与近似算法内容摘要：

成。 ||w)( 2nO 在算法的第二阶段中，非确定性地选择 V的一个 k元子集 V’V。 算法的第三阶段是确定性地检查 V’的团性质。 若 V’是一个团则接受输入，否则拒绝输入。 这显然可以在 时间内完成。 因此，整个算法的时间复杂性为。 )( 4nO)( 4nO非确定性算法在多项式时间内接受语言 CLIQUE， 故 CLIQUE∈NP。 16 多项式时间验证 VP={L|L∈∑* ， ∑ 为一有限字符集，存在一个多项式 p和一个多项式时间验证算法 A(X， Y)使得对任意 X∈∑* ， X∈L 当且仅当存在 Y∈∑* ， |Y|≤p(|X|) 且 A(X， Y)=1}。 多项式时间可验证语言类 VP可定义为： 定理 91： VP=NP。 例如 (哈密顿回路问题 )：一个无向图 G含有哈密顿回路吗 ? 无向图 G的哈密顿回路是通过 G的每个顶点恰好一次的简单回路。 可用语言 HAMCYCLE 定义该问题如下： HAMCYCLE={G|G含有哈密顿回路 } 17 NP完全问题  PNP。  直观上看 ， P类问题是确定性计算模型下的易解问题类 ， 而 NP类问题是非确定性计算模型下的易验证问题类。  大多数的计算机科学家认为 NP类中包含了不属于 P类的语言 ， 即 P≠NP。  NP完全问题有一种令人惊奇的性质 ， 即如果一个 NP完全问题能在多项式时间内得到解决 ， 那么 NP中的每一个问题都可以在多项式时间内求解 ， 即 P=NP。  目前还没有一个 NP完全问题有多项式时间算法。 18 多项式时间变换 定义： 语言 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)∈。 *11 L *22 L 1L2L 1L2L*2*1 1L 2L*119 多项式时间变换 定理 92：设 L是 NP完全的，则 (1)L∈P 当且仅当 P＝ NP； (2)若 L∝ p ， 且 ∈ NP， 则 是 NP完全的。 1L 1L 1L定理的 (2)可用来证明问题的 NP完全性。 但前提是：要有第一个 NP完全问题 L。 20 9. 一些典型的 NP完全问题 部分 NP完全问题树 21 迄今为止，所有的 NP完全问题都还没有多项式时间算法。 对于这类问题，通常可采取以下几种解题策略。 (1)只对问题的特殊实例求解 (2)用动态规划法或分支限界法求解 (3)用概率算法求解 (4)只求近似解 (5)用启发式方法求解 NP完全问题的近似算法 22 近似算法的性能 若一个最优化问题的最优值为 c*， 求解该问题的一个近似算法求得的近似最优解相应的目标函数值为 c， 则将该 近似算法的性能比 定义为 =。 在通常情况下，该性能比是问题输入规模 n的一个函数 ρ(n) ， 即 ≤ ρ(n)。  cccc *,*m a x cccc *,*m a x 该 近似算法的相对误差 定义为 =。 若对问题的输入规模 n， 有一函数 ε(n) 使得 ≤ ε(n) ， 则称ε(n) 为该 近似算法的相对误差界。 近似算法的性能比ρ(n) 与相对误差界 ε(n) 之间显然有如下关系：ε(n)≤ρ(n)。