《参数计算简介（NP-难问题的算法设计与分析）.ppt》由会员分享，可在线阅读，更多相关《参数计算简介（NP-难问题的算法设计与分析）.ppt（35页珍藏版）》请在三一文库上搜索。
1、参数计算简介 (NP-难问题的算法设计与分析),冯启龙 ,第2页,提纲,NP完全理论 参数计算理论 分支界定 彩色编码 核心化,第3页,NP完全理论,多项式可解,P,NP难解问题,各领域中的可计算问题,最小生成树 最短路径 最大流问题 最大匹配问题 ,顶点覆盖 最大团 独立集 旅行商问题 ,NP完全理论,多项式可解,P,多项式可解,P,NP难解问题,多项式可解,P,NP难解问题,多项式可解,P,NP难解问题,多项式可解,P,最小生成树 最短路径 最大流问题 最大匹配问题 ,顶点覆盖 最大团 独立集 旅行商问题 ,最小生成树 最短路径 最大流问题 最大匹配问题 ,第4页,NP:在多项式时间内被验
2、证，仅回答Yes或No(判定问题),如何判定给定问题是否在NP中？,给定图G=(V, E)，问图G中是否存在V的一个大小不超过k的子集V，使得E中的任意一条边e, e至少有一个端点被包含在V中。,点覆盖,给定V的任意一个子集V1, 如果可在多项式时间内判定V1是否为点覆盖问题的解，则说明点覆盖问题在NP 中。,NP完全理论,第5页,给定完全图G=(V, E)，其中每条边赋有一定的权值，并给定参数K，问G中是否存在一条权值小于等于K且包括图中所有点的圈。,旅行商问题,给定G中的任意一个圈S, 可在多项式时间内判定S是否为旅行商问题的解。,NP完全理论,第6页,多项式规约,Q1 x,Q2 r(x)
3、,多项式时间,Yes,Yes,Yes,Yes,NP完全理论,第7页,NP-难,NP中的任意问题,Q,多项式规约,问题Q 是NP-难的,NP完全理论,第8页,NP-完全,NP-难 + 在NP中,Q,问题Q 是NP-完全的,NP完全理论,第9页,可满足性问题(Satisfiability),NP中的任意问题,可满足性问题,多项式规约,可满足性问题是NP-难的,NP完全理论,给定一个合取范式，是否存在对F中变量的一个赋值使得F为真?,可满足性问题,可满足性问题在NP中,可满足性问题NP-完全,第10页,怎样证明某个问题是NP难的？,Q1 x,Q2 r(x),多项式时间,Yes,Yes,Yes,Yes
4、,NP完全理论,第11页,关系图: P, NP, NP-难, NP-完全,NP完全理论,第12页,哪些问题是NP-难的, 但不是属于NP?,NP完全理论,判断任意一个给定程序是否会在有限的时间之内结束运行。,停机问题(Halting Problem),哪些问题属于NP, 介于P与NP-完全之间?,给定图G和H，判断G和H是否同构？,图同构问题(Graph isomorphism),给定整数N和M，判断N是否有一个比M小的因子?,整数分解(Integer factorization),第13页,参数复杂性(Parameterized Complexity),点覆盖,独立集,输入,图G, 整数k,
5、图G, 整数k,问题,是否可用k条点覆盖G中的所有边?,是否存在k个相互独立的点(两两之间没边)?,复杂性,NP-完全,NP-完全,枚举,O(nk),O(nk),O(2kn2),参数计算,不存在O(no(k)的算法,第14页,参数复杂性(Parameterized Complexity),如果参数化问题Q可在O(f(k)nc)时间内被求解,其中c为常数,则称Q是固定参数可解的。,固定参数可解(Fixed Parameter Tractable, FPT),基本思想,传统精确算法,指数底与n有关,参数算法,指数仅与k有关, n仅在多项式部分出现,第15页,参数复杂性(Parameterized
6、Complexity),参数计算理论对问题的难解性重新进行了划分：,NP难解问题,固定参数可解,O(f(k)nc),不存在O(f(k)nc)算法,固定参数不可解,寻找k大小的点覆盖,寻找长度为k的简单路径,寻找k个不相交的三角形,删除k个点使给定图无圈,最大团 独立集 支配集 ,第16页,参数复杂性(Parameterized Complexity),固定参数不可解,W框架，W1, W2.,Q1 (x, k),Q2 (x, k),固定参数可解规约,Q1 Yes,Q2 Yes,Q2 Yes,Q1 Yes,固定参数可解规约,O(f(k)nc),最大团 W1 独立集 W1 支配集 W2,第17页,参
7、数复杂性(Parameterized Complexity),Q1 (x, k),Q2 (x, k),固定参数可解规约,Q1 W1,Q2 W1,O(f(k)nc),W难度的证明,第18页,参数复杂性(Parameterized Complexity),NP-完全理论与参数计算理论的关系：,各领域中可计算问题,易解问题(P),难 解 问 题,难 解 问 题,固定参数可解,固定参数不可解,O(f(k)nc),W1, W2.,第19页,分支界定(Branch-and-Bound),给定图G(V, E)和正整数k，问V是否存在一个大小不超过k的子集V，使得E中的任意一条边至少有一个端点在V中。,点覆盖
8、问题(Vertex Cover),e=(x1, y1),x1,y1,e=(x2, y2),x2,y2,. . .,树中叶子的数量2k,k,第20页,分支界定,用T(k)表示在点覆盖集分支搜索树的大小=算法的运行时间,T(k) T(k-1)+T(k-1),T(k) 2k,T(k) T(k-1)+T(k-2),分支递归式的求解,1. 给出特征方程,xk=xk-1+xk-2,x2-x-1=0,2. 解特征方程,x1=(1+squrt(5)/2,x2=(1-squrt(5)/2,3. 基于方程根得分支复杂度,T(k) x1k,第21页,彩色编码(Color-Coding),给定图G=(V, E)，正整
9、数k，点s, t，寻找G中一条从s到t且含有k个中间点的简单路径，或返回G中不存在这样的简单路径。,k-(s, t)-路径问题,s,t,引入k种颜色1,2, k，将Vs, t中的点随机着色，使得从s到t简单路径上的k个中间点被着上了不同的颜色,第22页,彩色编码(Color-Coding),s,t,k=5,k个中间点被正确着色的概率（每个点被着了不同的颜色）,k个中间点总共的着色情况：,k个中间点被正确着色的情况：,kk,k!,k!/kk(k/2)k/kk=e-k.,第23页,彩色编码(Color-Coding),对于每次随机着色，k个中间点被正确着色的概率:,e-k,为了保证成功的高概率，重
10、复着色过程ek次,重复ek次着色过程，k个中间点仍没有被正确着色的概率：,(1-e-k)ek=e-10.38.,为了进一步降低错误的概率，可重复100ek次,错误的概率为：1/e100.,第24页,彩色编码(Color-Coding),s,t,假设G中从s到t含有k个中间结点的简单路径已被正确着色,怎样基于着色找到该路径？,Vs, t的点,C1,C2,C3,Ck,第25页,彩色编码(Color-Coding),Vs, t的点,C1,C2,C3,Ck,s,t,1,2,3,k,第i个点在哪个颜色筐中？(1 i k),枚举,枚举第1个点、第2个点、第k个点对应的所有可能颜色,k!,第26页,彩色编码
11、(Color-Coding),2,1,3,k,s,t,第27页,彩色编码(Color-Coding),2,1,3,k,s,t,怎样求解？,深度优先(Breath First Search),广度优先(Depth First Search),第28页,彩色编码(Color-Coding),算法的时间复杂度：,1. 基于着色对路径的求解：k!,2. 着色的次数：ek,3. 总的时间复杂度：ek k! |E|,如何改进？,第29页,彩色编码(Color-Coding),假设G中从s到t含有k个中间结点的简单路径已被正确着色,怎样基于着色找到该路径？,s,t,s,t,最优子结构,s,第i个点,如何基于
12、第i个点得到第i+1个点,第30页,彩色编码(Color-Coding),动态规划 对于图中的任一点v，需要记录从s出发到达v的彩色路径的可能颜色集。,s,t,v1,v1点记录的信息：,蓝,紫, 绿, 蓝, 黄, 绿,v2,v2点记录的信息：,蓝,紫, 绿, 黄, 红, 蓝, 黄, 红,第31页,彩色编码(Color-Coding),假设用Qi=C1, C2, Ch表示v点记录的从s出发到达v且长度为i的所有彩色路径对应的颜色集合。,h的取值范围：1 h (k choose i).,如何基于得到从s出发经过顶点v的长度为i+1的彩色路径。,for v的每一个邻居u do for j=1 to
13、h if u的颜色没有被包含在Cj 中 then Cj=Cj u的颜色; if Qi+1中没有一个集合用到的颜色与Cj相同 then Qi+1= Qi+1 Cj;,第32页,彩色编码(Color-Coding),算法的时间复杂度：,1. 基于着色对路径的求解：|E|2k,2. 着色的次数：ek,3. 总的时间复杂度：ek 2k|E|=(2e)k|E|,第33页,核心化(Kernelization),Q1 (x, k),Q2 (x, k),多项式时间,|x|=n, |x|=f(k),k=k,Q1 Yes,Q2 Yes,第34页,核心化(Kernelization),给定图G(V, E)和正整数k
14、，问V是否存在一个大小不超过k的子集V，使得E中的任意一条边至少有一个端点在V中。,点覆盖问题(Vertex Cover), 如果图G中存在0度点u，则删除点u, 对于G中的一度点v，假设v的邻居为u，则可直接把u点放入点覆盖中，k=k-1。,如果G 中存在度数大于等于k+1的点v，删除点v并且k=k-1,假设运用上述规则得到的点覆盖问题的新实例为(G(V, E), k),|V|=k2,核心化规则：,第35页,讨论,1. 分治法：什么问题可以应用分治法，什么问题不能用？,2. 动态规划：动态规划与分治法的关系 分治法能解得问题可不可以用动态规划解？ 动态规划可以解的问题可不可以用分治法解？,3. 理解最大独立集问题的NP-难证明 可满足性问题 规约到最大独立集问题,