《参数计算简介(NP-难问题的算法设计与分析)》由会员分享，可在线阅读，更多相关《参数计算简介(NP-难问题的算法设计与分析)（35页珍藏版）》请在金锄头文库上搜索。
1、参数计算简介 NP 难问题的算法设计与分析 冯启龙csufeng 第2页 提纲 NP完全理论参数计算理论分支界定彩色编码核心化 第3页 NP完全理论 多项式可解 P NP难解问题 各领域中的可计算问题 最小生成树最短路径最大流问题最大匹配问题 顶点覆盖最大团独立集旅行商问题 NP完全理论 多项式可解 P 多项式可解 P NP难解问题 多项式可解 P NP难解问题 多项式可解 P NP难解问题 多项式可解 P 最小生成树最短路径最大流问题最大匹配问题 顶点覆盖最大团独立集旅行商问题 最小生成树最短路径最大流问题最大匹配问题 第4页 NP 在多项式时间内被验证 仅回答Yes或No 判定问题 如何判
2、定给定问题是否在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页 多项式规约 Q1x Q2r x 多项式时间 Yes Yes Yes Yes NP完全理论 第7页 NP 难
3、 NP中的任意问题 Q 多项式规约 问题Q是NP 难的 NP完全理论 第8页 NP 完全 NP 难 在NP中 Q 问题Q是NP 完全的 NP完全理论 第9页 可满足性问题 Satisfiability NP中的任意问题 可满足性问题 多项式规约 可满足性问题是NP 难的 NP完全理论 给定一个合取范式 是否存在对F中变量的一个赋值使得F为真 可满足性问题 可满足性问题在NP中 可满足性问题NP 完全 第10页 怎样证明某个问题是NP难的 Q1x Q2r x 多项式时间 Yes Yes Yes Yes NP完全理论 第11页 关系图 P NP NP 难 NP 完全 NP完全理论 第12页 哪些问
4、题是NP 难的 但不是属于NP NP完全理论 判断任意一个给定程序是否会在有限的时间之内结束运行 停机问题 HaltingProblem 哪些问题属于NP 介于P与NP 完全之间 给定图G和H 判断G和H是否同构 图同构问题 Graphisomorphism 给定整数N和M 判断N是否有一个比M小的因子 整数分解 Integerfactorization 第13页 参数复杂性 ParameterizedComplexity 点覆盖 独立集 输入 图G 整数k 图G 整数k 问题 是否可用k条点覆盖G中的所有边 是否存在k个相互独立的点 两两之间没边 复杂性 NP 完全 NP 完全 枚举 O n
5、k O nk O 2kn2 参数计算 不存在O no k 的算法 第14页 参数复杂性 ParameterizedComplexity 如果参数化问题Q可在O f k nc 时间内被求解 其中c为常数 则称Q是固定参数可解的 固定参数可解 FixedParameterTractable FPT 基本思想 传统精确算法 指数底与n有关 参数算法 指数仅与k有关 n仅在多项式部分出现 第15页 参数复杂性 ParameterizedComplexity 参数计算理论对问题的难解性重新进行了划分 NP难解问题 固定参数可解 O f k nc 不存在O f k nc 算法 固定参数不可解 寻找k大小的
6、点覆盖 寻找长度为k的简单路径 寻找k个不相交的三角形 删除k个点使给定图无圈 最大团独立集支配集 第16页 参数复杂性 ParameterizedComplexity 固定参数不可解 W框架 W 1 W 2 Q1 x k Q2 x k 固定参数可解规约 Q1Yes Q2Yes Q2Yes Q1Yes 固定参数可解规约 O f k nc 最大团W 1 独立集W 1 支配集W 2 第17页 参数复杂性 ParameterizedComplexity Q1 x k Q2 x k 固定参数可解规约 Q1W 1 Q2W 1 O f k nc W难度的证明 第18页 参数复杂性 Parameterize
7、dComplexity NP 完全理论与参数计算理论的关系 各领域中可计算问题 易解问题 P 难解问题 难解问题 固定参数可解 固定参数不可解 O f k nc W 1 W 2 第19页 分支界定 Branch and Bound 给定图G V E 和正整数k 问V是否存在一个大小不超过k的子集V 使得E中的任意一条边至少有一个端点在V 中 点覆盖问题 VertexCover 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
8、 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 将V s t 中的点随机着色 使得从s到t简单路径上的k个中间点被着上了不同的颜色 第22页 彩色编码 Color Coding s t k 5 k个中间点被正确
9、着色的概率 每个点被着了不同的颜色 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 1 0 38 为了进一步降低错误的概率 可重复100ek次 错误的概率为 1 e100 第24页 彩色编码 Color Coding s t 假设G中从s到t含有k个中间结点的简单路径已被正确着色 怎样基于着色找到该路径 V s t 的点 C1
10、C2 C3 Ck 第25页 彩色编码 Color Coding V s 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 怎样求解 深度优先 BreathFirstSearch 广度优先 DepthFirstSearch 第28页 彩色编码 Color Coding 算法的时间复杂度 1 基于着色对路径的求解 k 2 着色的次数 ek 3 总的时间复杂
11、度 ekk 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的所有彩色路径对应的颜色集
12、合 h的取值范围 1 h k choosei 如何基于得到从s出发经过顶点v的长度为i 1的彩色路径 forv的每一个邻居udoforj 1tohifu的颜色没有被包含在Cj中thenCj Cj u的颜色 ifQi 1中没有一个集合用到的颜色与Cj 相同thenQi 1 Qi 1 Cj 第32页 彩色编码 Color Coding 算法的时间复杂度 1 基于着色对路径的求解 E 2k 2 着色的次数 ek 3 总的时间复杂度 ek2k E 2e k E 第33页 核心化 Kernelization Q1 x k Q2 x k 多项式时间 x n x f k k k Q1Yes Q2Yes 第3
13、4页 核心化 Kernelization 给定图G V E 和正整数k 问V是否存在一个大小不超过k的子集V 使得E中的任意一条边至少有一个端点在V 中 点覆盖问题 VertexCover 如果图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 难证明可满足性问题规约到最大独立集问题
