参数计算简介NP难问题的算法设计与分析.ppt
参数计算简介(NP-难问题的算法设计与分析),冯启龙,第2页,提纲,NP完全理论参数计算理论分支界定彩色编码核心化,第3页,NP完全理论,多项式可解,P,NP难解问题,各领域中的可计算问题,最小生成树最短路径最大流问题最大匹配问题,顶点覆盖最大团独立集旅行商问题,NP完全理论,多项式可解,P,多项式可解,P,NP难解问题,多项式可解,P,NP难解问题,多项式可解,P,NP难解问题,多项式可解,P,最小生成树最短路径最大流问题最大匹配问题,顶点覆盖最大团独立集旅行商问题,最小生成树最短路径最大流问题最大匹配问题,第4页,NP:在多项式时间内被验证，仅回答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,Q2r(x),多项式时间,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,Q2r(x),多项式时间,Yes,Yes,Yes,Yes,NP完全理论,第11页,关系图:P,NP,NP-难,NP-完全,NP完全理论,第12页,哪些问题是NP-难的,但不是属于NP?,NP完全理论,判断任意一个给定程序是否会在有限的时间之内结束运行。,停机问题(HaltingProblem),哪些问题属于NP,介于P与NP-完全之间?,给定图G和H，判断G和H是否同构？,图同构问题(Graph isomorphism),给定整数N和M，判断N是否有一个比M小的因子?,整数分解(Integer factorization),第13页,参数复杂性(Parameterized Complexity),点覆盖,独立集,输入,图G,整数k,图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 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页,参数复杂性(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中。,点覆盖问题(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)，正整数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,为了保证成功的高概率，重复着色过程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页,彩色编码(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个点,如何基于第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 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，问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-难证明可满足性问题 规约到最大独立集问题,
