第2章 NP完全理论.ppt

第2章NP完全理论 2 1下界 2 2算法的极限 2 3P类问题和NP类问题 2 4NP完全问题 2 5实验项目 SAT问题 2 1下界 对于任何待求解的问题 如果能找到一个尽可能大的函数g n n为问题规模 使得求解该问题的所有算法都可以在 g n 的时间内完成 则函数g n 称为该问题计算复杂性的下界 LowerBound 如果已经知道一个和下界的效率类型相同的算法 则称该下界是紧密 Close 的 意义 评价算法 改进算法 对问题的输入中必须要处理的元素进行计数 同时 对必须要输出的元素进行计数 这种计数方法产生的是一个平凡下界 OrdinaryLowerBound 2 1 1平凡下界 例 生成n个元素的所有排列对象的算法属于 n 平凡下界往往过小而失去意义 例 TSP问题的平凡下界是 n2 2 1 2判定树模型 判定树 DecisionTrees 是这样一棵二叉树 它的每一个内部结点对应一个形如x y的比较 如果关系成立 则控制转移到该结点的左子树 否则 控制转移到该结点的右子树 它的每一个叶子结点表示问题的一个结果 在用判定树模型建立问题的时间下界时 通常忽略求解问题的所有算术运算 只考虑分支执行时的转移次数 例 对三个数进行排序的判定树 2 1 3最优算法 所谓最优算法 OptimalityAlgorithm 是指在某一种度量标准下 优于该问题的所有 可能的 算法 如果能够证明求解问题 的任何算法的运行时间下界是 g n 那么 对以时间O g n 来求解问题 的任何算法 都认为是最优算法 2 2算法的极限 2 2 1易解问题与难解问题 2 2 2实际问题难以求解的原因 2 2 3不可解问题 2 2 1易解问题与难解问题 通常将存在多项式时间算法的问题看作是易解问题 EasyProblem 将需要指数时间算法解决的问题看作是难解问题 HardProblem 例 易解问题 排序问题 查找问题 欧拉回路难解问题 TSP问题 Hanio问题 Hamilton回路 为什么把多项式时间复杂性作为易解问题和难解问题的分界线 1 多项式函数与指数函数的增长率有本质的差别2 计算机性能的提高对多项式时间算法和指数时间算法的影响不同3 多项式时间复杂性忽略了系数 但不影响易解问题和难解问题的划分4 多项式时间复杂性的闭包性5 多项式时间复杂性的独立性 2 2 3不可解问题 不能用计算机求解 不论耗费多少时间 的问题称为不可解问题 UnsolubleProblem 例 不可解问题 停机问题 病毒检测作业 证明停机问题是不可解问题 2 3P类问题和NP类问题 2 3 1判定问题 2 3 2确定性算法与P类问题 2 3 3非确定性算法与NP类问题 2 3 1判定问题 一个判定问题 DecisionProblem 是仅仅要求回答 yes 或 no 的问题 判定问题的重要特性 证比求易 2 3 2确定性算法与P类问题 定义2 1设A是求解问题 的一个算法 如果在算法的整个执行过程中 每一步只有一个确定的选择 则称算法A是确定性 Determinism 算法 定义2 2如果对于某个判定问题 存在一个非负整数k 对于输入规模为n的实例 能够以O nk 的时间运行一个确定性算法 得到yes或no的答案 则该判定问题 是一个P类 Polynomial 问题 所有易解问题都是P类问题 2 3 3非确定性算法与NP类问题 定义2 3设A是求解问题 的一个算法 如果算法A以如下猜测并验证的方式工作 就称算法A是非确定性 Nondeterminism 算法 1 猜测阶段 在这个阶段 对问题的输入实例产生一个任意字符串y 在算法的每一次运行时 串y的值可能不同 因此 猜测以一种非确定的形式工作 2 验证阶段 在这个阶段 用一个确定性算法验证 检查在猜测阶段产生的串y是否是合适的形式 如果不是 则算法停下来并得到no 如果串y是合适的形式 则验证它是否是问题的解 如果是 则算法停下来并得到yes 否则算法停下来并得到no 定义2 4如果对于某个判定问题 存在一个非负整数k 对于输入规模为n的实例 能够以O nk 的时间运行一个非确定性算法 得到yes或no的答案 则该判定问题 是一个NP类 NondeterministicPolynomial 问题 关键 存在一个确定性算法 能够以多项式时间来检查和验证猜测阶段所产生的答案 例 NP类问题 Hamilton问题 P类问题和NP类问题的主要差别 P类问题可以用多项式时间的确定性算法来进行判定或求解 NP类问题可以用多项式时间的非确定性算法来进行判定或求解 17 65 TheMainQuestion PVersusNP DoesP NP Cook1971 Edmonds Levin Yablonski G del Isthedecisionproblemaseasyasthecertificationproblem Clay 1millionprize EXP NP P EXP P NP IfP NP IfP NP 2 1 2020 18 68 1 000 000problem P NP http www claymath org millennium Solved 2 4NP完全问题 2 4 1问题变换与计算复杂性归约 2 4 2NP完全问题的定义 2 4 3基本的NP完全问题 2 4 4NP完全问题的计算机处理 打工仔 垂头丧气老板 蠢材 滚 打工仔 大吼一声 无有效算法 老板 自己做不出来就说这个问题无解 滚 打工仔 那些大牛牛们也照样做不出来老板 原来是这样 那也难为你了 2 4 1问题变换与计算复杂性归约 定义2 5假设问题 存在一个算法A 对于问题 的输入实例I 算法A求解问题 得到一个输出O 另外一个问题 的输入实例是I 对应于输入I 问题 有一个输出O 则问题 变换到问题 是一个三步的过程 1 输入转换 把问题 的输入I转换为问题 的适当输入I 2 问题求解 对问题 应用算法A产生一个输出O 3 输出转换 把问题 的输出O 转换为问题 对应于输入I的正确输出 问题变换的一般过程 问题变换的主要目的不是给出解决一个问题的算法 而是给出通过另一个问题理解一个问题的计算时间上下限的一种方式 排序问题 输入I 是一组整数X x1 x2 xn 输出O 是这组整数的一个排列xi1 xi2 xin 配对问题 输入I是两组整数X x1 x2 xn 和Y y1 y2 yn 输出O是两组整数的元素配对 即X中的最小值与Y中的最小值配对 X中的次小值与Y中的次小值配对 依此类推 例 配对问题到排序问题的变换 配对问题到排序问题的变换有助于建立配对问题代价的一个上限 因为上述输入和输出转换都是在多项式时间完成 所以 如果排序问题有多项式时间算法 则配对问题也一定有多项式时间算法 假设存在算法A解决排序问题 则配对问题可以变换到排序问题 1 把配对问题的输入I转化为排序问题的两个输入I1 和I2 2 排序这两组整数 即应用算法A对两个输入I1 和I2 分别排序得到两个有序序列O1 和O2 3 把排序问题的输出O1 和O2 转化为配对问题的输出O 这可以通过配对每组整数的第一个元素 第二个元素 来得到 配对问题到排序问题的变换过程 定理2 3 计算时间下限归约 若已知问题 的计算时间下限是T n 且问题 可 n 变换到问题 即 n 则T n O n 为问题 的一个计算时间下限 定理2 4 计算时间上限归约 若已知问题 的计算时间上限是T n 且问题 可 n 变换到问题 即 n 则T n O n 为问题 的一个计算时间上限 定理2 5设 和 是三个判定问题 若 p 且 p 则 p 2 4 2NP完全问题的定义 定义2 6令 是一个判定问题 如果问题 属于NP类问题 并且对NP类问题中的每一个问题 都有 p 则称判定问题 是一个NP完全问题 NPCompleteProblem 有时把NP完全问题记为NPC P NP 广义上说 P类问题是可以用确定性算法在多项式时间内求解的一类问题 NP类问题是可以用非确定性算法在多项式时间猜测并验证的一类问题 而且P NP 目前人们猜测P NP 则P类问题 NP类问题 NP完全问题之间的关系如下 若P NP 则NPC P 定义2 7令 是一个判定问题 如果对于NP类问题中的每一个问题 都有 p 则称判定问题 是一个NP难问题 如果 是NP完全问题 是NP难问题 那么 他们之间的差别在于 必定是NP类问题 而 不一定在NP类问题中 一般而言 若判定问题属于NP完全问题 则相应的最优化问题属于NP难问题 NP完全问题和NP难问题的区别 2 4 3基本的NP完全问题 证明一个判定问题 是NP完全问题需要经过两步 1 证明问题 属于NP类问题 也就是说 可以在多项式时间以确定性算法验证一个任意生成的串 以确定它是不是问题的一个解 2 证明NP类问题中的每一个问题都能在多项式时间变换为问题 由于多项式问题变换具有传递性 所以 只需证明一个已知的NP完全问题能够在多项式时间变换为问题 NP完全问题的证明思想 一些基本的NP完全问题 1 SAT问题 BooleanSatisfiabilityProblem 2 最大团问题 MaximumCliqueProblem 3 图着色问题 GraphColoringProblem 4 哈密顿回路问题 HamiltonianCycleProblem 5 TSP问题 TravelingSalsmanProblem 6 顶点覆盖问题 VertexCoverProblem 7 最长路径问题 LongestPathProblem 8 子集和问题 SumofSubsetProblem 2 4 4NP完全问题的计算机处理 1 采用先进的算法设计技术2 充分利用限制条件3 近似算法4 概率算法5 并行计算6 智能算法 2 5实验项目 SAT问题 1 实验题目SAT问题也称为合取范式的可满足问题 一个合取范式形如 A1 A2 An 子句Ai 1 i n 形