算法2013s(L15)-NP完全性与近似算法.pptx

算法设计与分析
2018年3月7日
讲授内容:NP完全性与近似算法教师:胡学钢、吴共庆
纲要
判定问题与最优化问题
多项式时间归约
P、NP、NP-hard、NPC
NPC问题的证明方法
顶点覆盖问题
处理NP-hard问题
近似算法
2018/3/7
算法设计与分析-NP完全性与近似算法
2
举例
容易的和困难的问题


2-SAT问题vs. 3-SAT问题等
2018/3/7
算法设计与分析-NP完全性与近似算法
3
判定问题与最优化问题
最优化问题
问题的每个可行解都对应一个目标函数值,求解这类问题的目的是希望得到一个有最优目标函数值的可行解
判定问题
回答是否存在一个满足问题要求的解,即解只是简单的回答“是(1)”或“否(0)”。
通常可以把一个最优化问题转化为一个判定问题。例如,最短路径问题的目标是找一条从u到v的最短路径,优化的目标函数值是路径的边数。则相应的判定问题(Path)可以描述为:给定一个有向图G,顶点u和v,以及整数k,问图中从u到v是否存在一条最多k条边的路径。
2018/3/7
算法设计与分析-NP完全性与近似算法
4
多项式时间归约
用多项式时间归约算法的思想来证明特定的问题B不存在多项式时间算法
2018/3/7
算法设计与分析-NP完全性与近似算法
5
多项式时间归约
f
{0, 1}*
{0, 1}*
2018/3/7
算法设计与分析-NP完全性与近似算法
6
P类问题:多项式时间内可解的问题(判定/接受)
NP类问题:多项式时间内可验证的问题
P = NP ? lennium/
Solved???!!!!
$1,000,000 offered by Clay Mathematical Institute
P、NP、NP-hard、NPC
2018/3/7
算法设计与分析-NP完全性与近似算法
7
P、NP、NP-hard、NPC
定义给定语言L {0, 1}* , L是NP完全的(plete)当且仅当
(1) L ∈NP;
(2) 对于所有L' ∈NP,有L' ≤ P L 。
如果有一个语言L满足上述性质(2),但不一定满足性质(1),则称该语言L是NP难的(NP-hard)。并记NPC表示所有NP完全语言构成的语言类。NPC是NP中最难的问题。
2018/3/7
算法设计与分析-NP完全性与近似算法
8
P、NP、NP-hard、NPC
定理如果任何一个NPC问题多项式时间可解,则P=NP。等价地,如果NP中的任何问题没有多项式时间求解算法,则没有NPC问题是多项式时间可解的。
P
NP
NPC
NP-hard
2018/3/7
算法设计与分析-NP完全性与近似算法
9
NPC问题的证明方法
引理如果L是一个语言,对某个语言L'∈NPC ,使得L' ≤ P L ,则L是NP难的。而且,如果有L∈NP ,则L∈NPC。
证明:因为L'是NP完全的,对任意的L"∈ NP ,我们有L" ≤ P L',按照假设有L ' ≤ P L ,这样按照传递性,我们有L" ≤ P L ,这表明L是NP难的。如果L∈NP ,则由NP完全的定义,可知L∈ NPC,故所证成立。
2018/3/7
算法设计与分析-NP完全性与近似算法
10