《最新参数计算简介（np-难问题的算法设计与分析ppt课件.ppt》由会员分享，可在线阅读，更多相关《最新参数计算简介（np-难问题的算法设计与分析ppt课件.ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、参数计算简介（参数计算简介（NP-NP-难问题难问题的算法设计与分析）的算法设计与分析）第第2页页提纲提纲 NP完全理论完全理论 参数计算理论参数计算理论 分支界定分支界定 彩色编码彩色编码 核心化核心化第9页可满足性问题可满足性问题(Satisfiability)NP中的中的任意问题任意问题可满足可满足性问题性问题多项式规约多项式规约可满足性问题可满足性问题是是NP-NP-难的难的NP完全理论完全理论给定一个合取范式，是否存在对给定一个合取范式，是否存在对F中变量的一个赋值使得中变量的一个赋值使得F为真为真? 可满足性问题可满足性问题可满足性问题在可满足性问题在NP中中可满足性问题可满足性问
2、题NP-完全完全第10页怎样证明某个问题是怎样证明某个问题是NP难的？难的？Q1 xQ2r(x)多项式时间多项式时间YesYesYesYesNP完全理论完全理论第11页关系图关系图: P, NP, NP-: P, NP, NP-难难, NP-, NP-完全完全NP完全理论完全理论第12页 哪些问题是哪些问题是NP-难的难的,但不是属于但不是属于NP?NP完全理论完全理论判断任意一个给定程序是否会在有限的时间之内结束运行。判断任意一个给定程序是否会在有限的时间之内结束运行。 停机问题停机问题(Halting(HaltingProblem)Problem) 哪些问题属于哪些问题属于NP,介于介于P
3、与与NP-完全之间完全之间?给定图给定图G G和和H H，判断，判断G G和和H H是否同构？是否同构？图同构问题图同构问题(Graph isomorphism)(Graph isomorphism)给定整数给定整数N N和和MM，判断，判断N N是否有一个比是否有一个比MM小的因子小的因子? ?整数分解整数分解(Integer factorization)(Integer factorization)第13页参数复杂性参数复杂性(Parameterized Complexity)点覆盖点覆盖独立集独立集输入输入图图G, 整数整数k图图G, 整数整数k问题问题是否可用是否可用k k条点覆条点覆
4、盖盖G G中的所有边中的所有边? ?是否存在是否存在k k个相互独立的个相互独立的点点( (两两之间没边两两之间没边)? )?复杂性复杂性NP-完全完全NP-完全完全枚举枚举O(nk)O(nk)O(2kn2)参数计算参数计算不存在不存在O(no(k)的算法的算法第14页参数复杂性参数复杂性(Parameterized Complexity)如果参数化问题如果参数化问题Q Q可在可在O(f(k)nO(f(k)nc c) )时间内被求解时间内被求解, ,其中其中c c为常数为常数, ,则称则称Q Q是是固定参数可解的。固定参数可解的。 固定参数可解固定参数可解(Fixed Parameter Tr
5、actable, FPT)(Fixed Parameter Tractable, FPT)基本思想基本思想传统精确算法传统精确算法指数底与指数底与n有关有关参数算法参数算法指数仅与指数仅与k有关有关,n仅在多项式部分出现仅在多项式部分出现第15页参数复杂性参数复杂性(Parameterized Complexity)参数计算理论对问题的难解性参数计算理论对问题的难解性重新进行了划分重新进行了划分：NP难解问题难解问题固定参数可解固定参数可解O(f(k)nO(f(k)nc c) )不存在不存在O(f(k)nO(f(k)nc c) )算法算法固定参数不可解固定参数不可解寻找寻找k大小的点覆盖大小的
6、点覆盖寻找长度为寻找长度为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)nO(f(k)nc c) )最大团最大团W1独立集独立集 W1支配集支配集 W2第17页参数复杂性参数复杂性(Paramete
7、rized Complexity) Q1 (x, k) Q2(x, k)固定参数可解固定参数可解规约规约 Q1 W1 Q2 W1O(f(k)nO(f(k)nc c) )W难度的证明难度的证明第18页参数复杂性参数复杂性(Parameterized Complexity)NP-完全理论与参数计算理论的关系：完全理论与参数计算理论的关系：各领域中可计算问题各领域中可计算问题易解问题易解问题(P)难难解解问问题题难难解解问问题题固定参数可解固定参数可解固定参数不可解固定参数不可解O(f(k)nO(f(k)nc c) )W1, W2.第19页分支界定分支界定(Branch-and-Bound)给定图给
8、定图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)表示在点覆盖集分支搜索树的大表示在点覆盖集分支搜索树的大小小= =算法的运行时间算法的运行时间T(k)T(k) T(k-1)+T(k-1)T(k-1)+T(k-
9、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. 基于方程根得分支复杂度基于方程根得分支复杂度T(k)T(k) x1k 第21页彩色编码彩色编码(Color-Coding)给定图给定图G=G=( (V, EV, E)
10、)，正整数，正整数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个中间点被着上了不同的颜色个中间点被着上了不同的颜色第22页彩色编码彩色编码(Color-Coding)s st tk=5k=5k k个中间点被正
11、确着色的概率（每个点被着了不同的颜色）个中间点被正确着色的概率（每个点被着了不同的颜色）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为了保证成功的高概率，重复着色过程为了保证成功的高概率，重复着色过程e ek k次次重复重复e ek k次着色过程，次着色过程，
12、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, tVs, t的点的点C1C1C2C2C3C3CkCk第25页彩色
13、编码彩色编码(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怎样求解？怎样求解？深度优先深度优先(Breath First Search)(
14、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个中间结个中间结点的简单路径已被正确着色点的简单路径已被
15、正确着色怎样基于着色找到该路径？怎样基于着色找到该路径？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点记录的信息：点记录的信息：蓝蓝, ,紫紫, , 绿绿, , 黄黄, ,
16、 红红, , 蓝蓝, , 黄黄, , 红红第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 t
17、o h for j=1 to h if u 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. 总的时间复杂度：总的
18、时间复杂度：e ek k 2 2k k|E|=(2e)|E|=(2e)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)(Ver
19、tex 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-难证明难证明可满足性问题可满足性问题 规约到最大独立集问题规约到最大独立集问题