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