《高级算法设计》课件 第3、4章 NP问题；近似算法

高级算法设计与分析NP问题主要内容基本概念、归约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问题顶点覆盖问题顶点覆盖问题顶点覆盖问题顶点覆盖问题哈密顿回路哈密顿回路哈密顿回路证明哈密顿回路哈密顿回路哈密顿回路可以这样定义附件图吗？哈密顿回路用附件图替换哈密顿回路用附件图替换哈密顿回路多项式转换哈密顿回路以上过程是一种归约哈密顿回路以上过程是一种归约高级算法设计与分析近似算法目录概述旅行商问题子集和问题集合覆盖-整数规划斯坦纳最小树概述NPC问题该如何求解?如果规模很小，用指数运行时间算法对一些特殊的情况，如果有多项式时间可以解决，则设计多项式算法对用一般情况，则通过多项式时间的近似解法概述近似解的精确度C：某一算法解的代价C*：最优解的代价如果一个解达到此因子，则称算法C为ρ(n)近似算法概述近似模式：对于一个输入为n的实例，通常近似算法的因子为（1+ε）算法时间除了和n相关，和ε也相关如果对于任意一个ε>0，该算法都可以在输入规模为n的多项式时间内完成，称此模式为多项式时间近似模式显然此种模式下，当ε趋近于0时，算法逼近最优值，但可能算法的复杂度急剧增加，如时间复杂度为多项式时间近似模式中一种更好的模式称为完全多项式时间近似模式，其复杂度为：这种模式当ε减少时，运行时间不会指数增长，而是多项式增长旅行商问题旅行商问题为NPC问题定义：对于完全无向图G=（V，E），设c(A)为子集A的总代价三角不等式：旅行商问题满足三角不等式的旅行商问题生成最小生成树按对树进行先序的顺序访问节点上述算法中，生成最下生成树可以用Kruskal算法或者Prim算法，复杂度都为O(mlogn)。先序遍历的复杂度为O(n)，所以旅行商问题的近似算法复杂度为O(mlogn)

旅行商问题旅行商问题最优旅行线路（H*）的总代价的下限为最小生成树（T）边的总代价对T进行按先序往返（返回时会再次遍历节点）遍历（W），W刚好对所有的边遍历两次旅行商问题一般旅行商问题三角不等式不成立的条件下，ρ近似的旅行商问题是一个NPC问题，则定理自然成立旅行商问题如果图G存在一条哈密顿回路H，则G′必然存在一条代价为n的旅行商回路TSP(同H),此回路为ρ近似旅行商回路如果图G′存在一条ρ近似的旅行商回路TSPρ，则图G必然存在一条哈密顿回路H

子集和问题准确算法（指数时间复杂度）:得出集合S的所有子集，并计算所有子集的和优化在第i-1轮迭代中，计算(e1,e2,…,ei-1)所有的子集和在第i轮迭代中，计算(e1,

e2,…,ei)在相加的过程中，一旦子集和超过t，舍弃子集和问题子集和问题去除相近的元素：x可以被y代替例子子集和问题子集和问题子集和问题子集和问题子集和问题按这两种不同的情况讨论子集和问题子集和问题子集和问题所以：子集和问题子集和问题Ln必然包含0元素，可能包含1元素集合覆盖问题简单集合覆盖

集合覆盖问题：例子集合覆盖问题贪心算法集合覆盖问题算法第i次选择了子集Si加入到顶点覆盖集R，则其总代价+1在选取第i个子集Si时，假设ni个元素被Si首次覆盖，其中每个元素分配到的代价为：集合覆盖问题集合覆盖问题当近似算法选择了i个子集后，子集S中未被覆盖的元素的个数集合覆盖问题集合覆盖问题集合覆盖问题集合覆盖-整数规划带权重的集合覆盖：覆盖所有的元素，其权重总和最小设E={1,2,3,4,5,6,7,8}子集有:S1={1,2,3}w1=1S2={2,7,8}w2=2S3={4,5,6,7}w3=3S4={4,5,6,8}w4=4解:C={S1,S2,S3},C={S1,S2,S4}最优解：C={S1,S2,S3}集合覆盖-整数规划松弛集合覆盖-整数规划算法元素的最大频率f：设g表示包含某一元素的子集个数，则最大的g即元素的最大频率f在所有的LP最优解的子集中，选取xi（每个子集通过LP求解得出的值）的值大于1/f的子集作为IP的解集合覆盖-整数规划证明1：以上选取的子集包含了E中所有的元素集合覆盖-整数规划集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法斯坦纳最小树斯坦纳最小树用最小生成树来近似斯坦纳树？斯坦纳最小树斯坦纳最小树：例子GRTMTGMTTST斯坦纳最小树：例子算法基于原图G，生成R的一个完全图GR，其中任意一条边的权重为原图G中的最短路径基于GR，生成最小生成树TMT

将TMT

中的边替换成原来的最短路径，得到图GMT