算法分析与设计2007第a讲

第 A 讲 第 1 页 上次内容 1 先行约束排工 限制很强时是多项式可解的 没有限制是 NP Complete 2 着色问题 限制顶点度不超过 4 的图 3 着色问题是 NPC 限制平面图的 3 着色问题是 NPC 3 拟多项式变换与 NPC 类 划分问题的拟多项式算法 划分问题拟多项式时间算法 一个问题中有两个参数影响时间复杂度 划分问题 输入长度 Length I A log2 A A log2 Aa i i aS 最大数值 问题的实例中碰到的最大数值 Max I B Aa i i aS 说明 可以设计算法与两个参数有关系 一个问题的编码不是完全相同的 因此输入长度和最大数值会根 据编码不同有所不同 一般来说 不管用什么样的编码 输入长 度是差不多的 多项式相关的 不同人编不同的程序 有的问题根本不含有数值参量 这样 MAX I 0 划分问题算法时间复杂性 O nB 定义 6 1 拟多项式算法 判定问题 存在解答算法 算法的时间 复杂度为 T I P Length I Max I I 为任意实例 则该算法称为 求解问题 的拟多项式算法 看问题 最好讲讲怎样问题怎样在计算机输入 首先明确输入长度为 n 则最 大数值可能是2n 1 SAT 该问题中根本没有 Max I 这一项 没有最大数值 Max I 0 第 A 讲 第 2 页 2 团问题 最大数值 J V 自然受到限制 3 TSP 该问题中边长或 K 是最大数值 Max I 项 4 划分问题 元素重量是 Max I 项 O nB 考虑 1 Max I 0 这个问题是 NPC 的 可以认为 最大数值本身 受到输入长度的限制 Max I P Length I 考虑问题 2 团问题中的数值参量受到输入长度约束 J V Max I P Length I 3 TSP 问题中 边长根本不受输入长度的约束 每条边长可能很大 问题 3 的元素重量也不受到输入长度约束 函数 P 不存在 使 Max I P Length I 4 划分问题中 元素价值不受输入长度的约束 函数 P 不存在 使 Max I P Length I 受约束的含义 存在多项式函数 P 使 Max I P Length I n 位输入 则数值大小为 2n Max I 2Length I P Length I Max I P Length I 2 ILength 定义 6 2 对于判定问题 若不存在多项式函数 P 使对所有实例 I 有 Max I P Length I 则称 为数问题 最大数值不受约束 就是最大数值可能很大的问题是数问题 不受输入长度约束 命题 6 1 若判定问题是 NPC 类 不是数问题 P NP 则该问题不 能被拟多项式算法解答 解释什么问题不是数问题 第 A 讲 第 3 页 证明 T q Length I Max I q length I p length I q1 length I 若有拟多项式算法 则有多项式算法 则 P NP 矛盾 下面是几个 问题 多项式函数 P D 表示该问题的所有实例组成的集合 定 义一个新的实例集合 D P I I D Max I P Length I 由 D P 中实例表达的问题就是多项式可解的吗 注意多项式函数给定 再次强调问题是实例的集合 I D I D P 定义 6 3 判定问题 存在多项式函数 P 使 P是 NPC 的 则称 是强 NPC 的 命题 6 2 若问题 是强 NPC 的 P NP 则一定不能被拟多项式算 法解答 强 NPC 问题不能有拟多项式算法 否则 NPC 问题就可以多项式解答了 受限子问题是 NPC 的 能被多项式时间算法解答 则任意 NP 问题都能被多项式时间算法 解答 6 2 证明强 NPC 与拟多项式变换 先证明货郎问题是强 NPC 的 限制货郎问题的边长不是很大 也是 NPC HC TSP 第 A 讲 第 4 页 HC 实例为 a e d c b a e d c b 1 1 1 1 1 1 1 2 2 1 将该实例变为货郎问题实例如下 d a b d a c d a d d a e d b c d c d d c e d d e 1 d b d d b e 2 常数 K 5 显然 若 HC 实例存在 hamilton 回路 则相应 TSP 实例存在不超过 K 的旅游 若 TSP 实例存在不超过 K 的旅游 则 HC 实例存在 hamilton 回路 每条边的长度不超过 2 可以认为 Max I 2n 满足下式否 Max I Length I 满足这种限制的 TSP 仍然是 NPC 的 所以 TSP 问题是强 NPC 的 对于一个 NPC 问题 如果你能说明其受限子问题是 NPC 的 则就 说明这个问题是强 NPC 的 货郎问题就不可能有拟多项式算法 P Max I Length I P 2n q n 拟多项式算法就是多项式算法 先讲一个问题 3 划分问题 第 A 讲 第 5 页 实例 讲清楚 但不证明 1 集合 A 含有 3m 个元素 A a1 a2 a3m 2 S ai Z 3 存在正整数 B Z 满足 B 4 S ai B 2 4 mBaS Aa i i 询问 是否存在 A 的划分 A S1 S2 Sm 即将 A 划分为 m 个子 集 使 B ii Sa i aS 简单解释 三划分不是划分为三份 1 划分的每个子集中肯定是 3 个元素 因为 B 4 S ai B 2 2 每个集合中 3 个元素 就是 3 划分的含义 有很多东西 我们不讲了 4 划分是强 NPC 3 划分也是强 NPC 说明 不要看书上有很复杂的符号 很多内容 实际当你看懂得时 候也很简单 下面先定义什么是拟多项式变换 D 1P D 1 D 2 D 2q 定义 6 4 1 判定问题 1和 2 实例集合分别为 D 1 D 2 第 A 讲 第 6 页 2 回答 yes 的实例集合为 Y 1和 Y 2 3 两个问题的实例编码后分别有 Length I Max I Length f I Max f I 4 存在一个变换 f D 1 D 2 满足 a 对任意实例 I D 1 计算 f I 的时间复杂度是 Length I 和 Max I 的 多项式函数 T f I P Max I Length I b 对 I D 1 I Y 1当且仅当 f I Y 2 c 存在多项式函数 p1使对 I D 1有 Length I p1 Length f I 这个限制很有用 I 的长度不能很大 仔细研究研究的话 估计这个条 件可以去掉 Length f I p2 Length I Max I 这个由前面就能得到 d 存在两个变量的多项式函数 q1 使 Max f I q1 Max I Length I 则 f 称为 1到 2的拟多项式变换 变换与数值和长度都有关 说明 如果数值量受到输入长度限制 就是多项式时间变换 条件 a b 是拟多项式变换的基本要求 变换计算时间复杂度要 求更宽一些 c Length f I p2 Length I Max I d 要求 Max 不能增大到超过 Max 和 Length 的界定范围 第 A 讲 第 7 页 引理 6 1 是强 NPC 是 NP 问题 存在一个 到 的拟多项式变 换 则判定问题 也是强 NPC 的 证明 将 和 中的最大数值都限定受输入长度的多项式限制 则受 限制的 是 NPC 问题 存在的拟多项式变换就是多项式变换 所以 受限制的 是 NPC 的 所以不受限制的 是强 NPC 的 实例 有限任务集合 T t1 t2 tn 只有一台机器 r tk 最早起始时间 d tk 最晚结束时间 L tk 加工长度 询问 是否存在排工表 tk k 1 2 n 使 d tk L tk tk r tk 每个任务都能按时完成 任意 ti tj i j ti tj max L ti L tj 将前面的区间排工拷贝过来的 定理 6 3 区间排工是强 NPC 证明 三划分 P区间排工 三划分的实例 A a1 a2 a3 a3m S ai Z B Z 由此构造区间排工实例 T A t1 t2 tm 1 L t1 L t2 L tm 1 1 L ai S ai i 1 3m 第 A 讲 第 8 页 r ti iB i 1 i 1 m 1 d ti iB i i 1 m 1 r ai 0 i 1 3m d ai mB m 1 说明 mB m 1 所以从 0 开始 总用时间是 mB m 1 31 11 mm ii ii L aL t t1 t2 t3 tm 1 B B 1 2B 1 2B 2 3B 2 3B 3 m 1 B m 2 mB m 1 B B B B 1 变换可以在三划分实例输入长度的多项式时间内完成 2 若三划分实例回答 yes 则变换后的区间排工实例也回答 yes 若 区间排工实例回答 yes 则相应三划分实例一定有一个三划分 3 条件 c 几乎总是满足 Length I p1 Length f I 4 最大数值变化不大 符合条件 d 三划分中的最大数值为 B 区间 排工的最大数值为 mB m 1 当然是 B 的多项式函数 所以是强 NPC 子林同构 实例 图 G 和 H 询问 图 G 是否包含一个子图与 H 同构 限制 G 和 H 都是树 则该问题是多项式时间可解的 限制 G 为树 H 为林 则该问题是强 NPC 首先判定两个图是否完全同构也是多项式时间可解的 子林同构问 第 A 讲 第 9 页 题根本就没有数值参量 所谓强 NPC 与 NPC 等价的 这个例子的 意义在于说明可以用证明强 NPC 的方法证明 NPC 定理 6 4 子林同构问题是强 NPC 证明 三划分拟多项式变换到子林同构 A a1 a2 a3m S ai B Z 构造 G 和 H 如下 B 1 个点 G H 构造为 1 2 ai S ai 个点的线 S ai 个点的线 首先说明若三划分回答 yes 则显然可以将对应的 H 的线图接起来 对到 G 上去 另外若 H 中的线图接到星图上形成完全 G 的形状 则接到每一条线 上去的线段的总长均为 B 所以原来的三划分问题一定可以三划分 第 A 讲 第 10 页 3 变换的时间复杂度与 B 有关 变换出来的树的点的个数与 B 有关 主要说明 限制 B 不大时 即为输入长度的多项式函数时 三划分问题是 NPC 的 变换本身是输入长度和最大数值的多项式函数 所以是多项式变 换 所以子林同构是 NPC 的 子林同构中根本没有数值参量 当然是强 NPC 的 6 3 复杂性类之间的关系 很多问题不是 NP 的 所以不是 NPC 的 但是比 NPC 问题更难 这样的问题怎样说明难度 Hamilton 问题补问题 实例 无向简单图 G V E 询问 图 G 没有 hamilton 回路吗 这个问题不是多项式时间可验证的 不是 NP 的 所以不能说是 NPC 的 这个问题能够正确回答 则 hamilton 回路问题也能正确回 答 Tsp 优化问题 实例 城市集合 C C1 Cm 城市之间距离 d Ci Cj 询问 求城市排列 使 1 C 2 C m C 第 A 讲 第 11 页 min C 1C 2 C m为城市排列 m i ii CCd 1 1 m i ii CCd 1 1 这个问题也不是 NP 的 所以不是 NPC 的 这个问题能够正确回答 货郎判定问题也能正确回答 在问题中要找一个解的问题称为搜索问题 多项式归约多项式归约 本身就说明一件事本身就说明一件事 若若 2能多项式时间正确解答能多项式时间正确解答 则则 1也能多项式时间正确解答也能多项式时间正确解答 所以有 turing 规约的概念 图灵规约是多项式变换概念的推广 先举个例子 先举个例子 假设货有一个货郎优化问题的算法为假设货有一个货郎优化问题的算法为 A 设计货郎判定问题求解算法如下 假设货郎判定问题的实例为设计货郎判定问题求解算法如下 假设货郎判定问题的实例为 G d K 1 调用算法调用算法 A G d 求得最优解 设得到的最短旅游长度为求得最优解 设得到的最短旅游长度为 OPT G d 2 若若 OPT G d K 则回答 则回答 yes 否则回答 否则回答 n