《高级算法设计》课件 第3章 NP问题

高级算法设计与分析NP问题林海lin.hai@B站：foretmer主要内容基本概念、归约P问题的证明NPC问题的证明算法效率多项式时间算法O(nc)forsomeconstantc非多项式时间算法复杂度为O(n)的算法是高效率?复杂度为O(nlogn)?O(n2)?O(n10)?O(nlogn)?O(2n)?O(n!)?基本概念：P问题基本概念：NP问题基本概念：NPC问题基本概念：关系P问题，NP问题和NP完全问题的关系（认为，没有得到证实）基本概念：NPC问题判断是否NP问题也就是给出一个证书，可否在多项式时间内判断它是否是原问题的一个解最优化问题需要转化为判断性问题基本概念：NPC问题旅行商问题转化为：此图中是否存在总权重为1的回路?此图中是否存在总权重为2的回路?…此图中是否存在总权重为n的回路?一个优化问题可分解为多个判定性问题如果能够证明一个判定性问题为NP难时，显然原问题也是NP难的基本概念：归约性通俗的讲，一个问题(如Q1)可以规约为另外一个问题(如Q2)是指问题Q1可以转换为问题Q2，之后可以通过求解Q2的方法来求解Q1如:求解一元一次方程(问题Q1)可归为求解一元二次方程(问题Q2):一元二次方程的二次项系数为0即可，之后可以通过求解一元二次方程的方法来求解一元一次方程基本概念：归约基本概念：归约归约具有传递性如果问题A可归约为问题B，问题B可归约为问题C，则问题A一定可归约为问题C。基本概念：归约证明基本概念：归约性主要内容基本概念、归约P问题的证明NPC问题的证明P问题的证明2合取范式(CNF)的可满足性问题(SAT)P问题的证明2合取范式(CNF)到图的转换

P问题的证明2合取范式(CNF)到图的转换

P问题的证明2合取范式(CNF)到图的转换当且仅当2CNF中存在子句(x∨y)，图G中存在边¬x→y

(和边¬y→x)P问题的证明P问题的证明P问题的证明P问题的证明P问题的证明主要内容基本概念、归约P问题的证明NPC问题的证明NPC问题的证明第一个NPC问题电路可满足性问题问题：给定一个逻辑电路，问是否存在一种输入使输出为True其它的NPC问题都是由这个问题归约而来的。因此，逻辑电路问题是NPC类问题的“鼻祖”。有了第一个NPC问题后，一大堆NPC问题就出现了，因为再证明一个新的NPC问题只需要将一个已知的NPC问题归约到它就行了公式可满足性问题公式可满足性问题:公式可满足性问题公式可满足性证明这是一个NP问题公式可满足性问题公式可满足性证明归约证明：电路可满足性归约到公式可满足性显而易见，每个电路都可写成一个布尔公式也就是存在f，使得任何一个实例x属于电路，当且仅当f(x)属于公式但，直接写的话，因每个电路门输出线扇出为2或者2以上导致布尔公式的规模出现指数增长公式可满足性问题公式可满足性证明我们的目的不是将电路转换为布尔公式，而是证明可满足性，如果电路有可满足指派，则电路每个门输出都由其输入决定，写成表达式如右x7公式可满足性问题公式可满足性证明以上转换为多项式时间如果电路有可满足性实例，则电路输出为1，而公式输出也为1如果公式输出为1，则显然电路输出也为1公式可满足性为NPC问题3-CNF可满足性问题每个子句有3个文字3-CNF可满足性问题公式可满足性证明这是一个NP问题公式可满足性可以归约到3-CNF将布尔公式转换为子句的合取式将子句转换为合取范式将子句转为3个文字的合取取式3-CNF可满足性问题1.将布尔公式转换为子句的合取式建立布尔公式的语法树3-CNF可满足性问题1.将布尔公式转换为子句的合取式建立布尔公式的语法树将语法分析树看成电路，得出归约的布尔公式此布尔公式为合取式3-CNF可满足性问题2.将子句转换为合取范式构造每个子句的真值表3-CNF可满足性问题2.将子句转换为合取范式构造每个子句的真值表根据真值表中值为0的项，得出析取范式此析取范式等价于子句的否3-CNF可满足性问题2.将子句转换为合取范式构造每个子句的真值表根据真值表中值为0的项，得出析取范式此析取范式等价于子句的否运用德摩根定律，得出合取子句（将析取范式再取否）3-CNF可满足性问题3.将子句转为3个文字的合取取式3-CNF可满足性问题以上映射为多项式时间将布尔公式转换为子句的合取式同布尔电路转换为布尔公式将子句转换为合取范式每个子句至多变为8个子句（至多3个变量）将子句转为3个文字的合取取式至多引入4个子句由以上步骤可知：3-CNF是可满足的当且仅当以上三个步骤的每一步都是可满足的=》以上转换为归约团问题团问题团问题证明这是一个NP问题团问题3合取范式可以归约为团问题构造图一个子句对应一组顶点对于任意两个在不同组的顶点，如果满足“这两个顶点不是‘否’的关系”这一条件，就用一条边连接团问题是一组可满足赋值，其对应图中的灰色团团问题团问题还有一个疑问：归约为一个特殊的图，能说明一般图的团问题也是NP完全的吗？顶点覆盖问题顶点覆盖问题顶点覆盖问题证明这是一个NP问题顶点覆盖问题顶点覆盖问题顶点