算法分析与设计2009第b讲

上次内容 1 什么是拟多项式算法 PESEUDO polynomial 在考虑问题实例描述的两个参数 Max I Length I 2 什么是拟多项式变换 什么是数问题 3 什么是强 NPC 问题 限制数不很大时也很难解 数值参量受限时亦为 NPC 的 4 什么是 NP hard 问题 Turing 规约 神喻图灵机 5 NPC 问题对应的优化形式都是 NP hard 问题 图灵规约与拟多项式变换完全是两件事 图灵归约 1 2 要说明若 2有多项式时间求解算法 则 1也有多 项式时间求解算法 设求解 2的算法为 A2 有一个将 1实例转换为 2实例的变换 f I f I 设计求解 1的算法 A1 I 其中调用 A2 f I 1 若若 A2 能求得满足条件的解 则能求得满足条件的解 则 A1 求得的解也满足条件 求得的解也满足条件 2 若若 A2 时间复杂度为时间复杂度为 O 1 则 则 A1 时间复杂度是多项式时间复杂度 时间复杂度是多项式时间复杂度 实际可以假设 A2 f I 的计算不需要时间 这样就叫 1图灵归约到 2 NP Hard 的定义 一个问题是 NPC 的 则该问题推广称为 NP hard 问题 若 1是 NP hard 问题 1可以图灵归约到 2 则 2也是 NP hard 问 题 TSP 优化问题 实例 城市集合实例 城市集合 C C1 Cm 城市之间距离 城市之间距离 d Ci Cj 询问 求城市排列 询问 求城市排列 使 使 1 C 2 C m C min C 1C 2 C m为城市排列为城市排列 m i ii CCd 1 1 m i ii CCd 1 1 定理 TSP 优化问题是 NP hard 证明 TSP 判定问题图灵归约到 TSP 优化问题 TSP 判定问题是 NPC 所以是 NP Hard 设存在 TSP 优化问题求解算法 A 设计 TSP 判定问题的算法如下 1 对于给定 TSP 判定问题的给定实例 G d K 调用 A G d 求得城市 排列 21m CCC 2 若 K 则回答 Yes 否则回答 No m i ii CCd 1 1 若 A 是多项式算法 则上述算法能够在多项式时间解答 所以 TSP 优化问题是 NP hard 问题 说明货郎优化问题有多项式算法 则货郎判定问题有多项式算法 下面说明货郎判定问题有多项式算法 则货郎优化问题有多项式算法 货郎延伸问题 实例 1 城市集合 C C1 C2 Cm 2 任意两个城市之间的距离 d Ci Cj Z 3 正整数界值 B Z 4 C 中 K 个城市的部分旅游 C 1 C 2 C k 询问 是否可将 延伸为一个长度不超过 B 的全程旅游回路 C 1 C 2 C k C k 1 C m C 1 定理 货郎延伸问题是 NP hard 证明 将货郎优化问题图灵归约到货郎延伸问题 即如果货郎延伸问题有多项式算法 则货郎优化问题有多项式算法 S C d B 为解答货郎延伸问题的算法 设计货郎优化算法如下 折半法折半法 1 Bmin m Bmax m max d ci cj ci cj C 最大就这么大 2 若 Bmax Bmin 0 则 B Bmin 暂停 3 Bmid Bmin Bmax 2 4 调用子程序 S C d Bmid 若回答 yes 则 Bmax Bmid 转 2 否则 Bmin Bmid 转 2 最优解值为 B 最优解怎么求 S C d B S C d B S C d B 由此确定 C 2 S C d B S C d B S C d B 由此确定 C 3 5 C 1 C1 6 for i 2 to m do for j 1 to m do 若 Cj C1 C 2 C i 1 且 S C d B 回答 yes 则 C i Cj 没有判定货郎延伸是否 NP 但是已经将货郎优化问题图灵归约到货郎延 伸问题 这样最后求得 C1 C 2 C i 1 C m 为最优解 还有第 k 个最大子集问题是 NP Hard 证明自己看 货郎延伸图灵规约到货郎判定怎么办 设货郎判定问题算法为 TD C d K C 1 C k C 1 C k D1 d C 1 C 2 d C k 1 C k K1 K D1 只要存在一条回路长度不大于 K1 原来实例即回答 Yes 设 C c 1 c 2 c k c1 c2 c3 最短的旅游回路为如下情况之一 c1 c 1 c 2 c k c2 c 1 c 2 c k c3 c 1 c 2 c k 所以图灵规约为 算法 S C d B 1C1 C c 1 c 2 c k c0 K B 1 1 1 k ii i d cc 2For every cx C1 c0 3 ds c0 cx d c 1 cx 4For cy C1 c0 cx 5 ds c0 cy d c k cy 6If TD C1 ds K YES return YES 7 8Return NO 第 7 章 NP 难解问题近似算法 只讲近似算法 不讲概率算法 含义 虽然不能得到最优解 但能离最优解不远 达不到最好 力争更好 7 1 近似算法及其性能评估 符号 D I D 求解的目标是最大化或最小化的优化问题 询问时要求解 按照解的格式 并满足解的条件 S I 可行解集 现在不求最优解了 只要符合解的格式就叫可行 解 M I S 对于 I D S S I 表示解值 解的数值 总是用一个数 值衡量解的优化程度 S S I 表示最优解 显然有 M I S M I S 最小优化问题 最小优化问题 M I S M I S 最大优化问题 最大优化问题 通常用 OPT I M I S 表示最优解值 通常将实例 I 的最优解的解 值记为 OPT I 假设有算法 A 对于任意实例 I 都能找到最优解 A I OPT I 则 称算法 A 为求解问题 的精确算法 也有很多问题能够求得最优解 有时总也求不到最优解 可以求出一个解 解的格式符合规则 但 不能保证求到最优解 求出的解只是可行解 定义 给定问题 若有算法 A 存在一个常数 K 0 使得所有实例 I D 总有 A I OPT I K 则称算法 A 为解答问题 的绝对近似算法 若 A 为多项式时间算法 则称 A 为解答问题 的多项式时间绝对近似算法 已知当 P NP 时 NP hard 优化问题不存在多项式时间算法 但其 中有些问题存在多项式时间绝对近似算法 存储最多程序问题 实例 n 个程序 每个程序的存储容量分别为 L1 Ln 两个磁盘 存储容量都是 L 询问 若不允许一个程序同时存在于两个磁盘内 求两个磁盘最多求两个磁盘最多 能存储程序的个数能存储程序的个数 这个问题是 NP hard 将划分问题图灵规约到该问题就能证明 假设 L1 L2 Ln 2L 即可 现在设计一个算法 贪心算法 1 对 n 个程序 按其存储容量的非降顺序排序 L1 L2 Ln 2 按程序编号从 1 到 n 依次向磁盘 1 存放程序 直到磁盘 1 放不 下为止 3 再转向存储磁盘 2 按照顺序依次向磁盘 2 存储程序 直到磁盘 2 不能存放为止 这个算法的时间复杂度为 O nlogn 定理 7 1 设 I 是存储最多程序问题的任意实例 OPT I 为其最优解 的解值 A I 为算法 A 所求出的解的解值 有 OPT I A I 1 即算法 A 为多项式时间绝对近似算法 证明 考虑一个容量为 2L 的磁盘 按照 L1 Ln的顺序存入磁盘可 以存 p 个程序 OPT I p 两个磁盘按照前面算法 最少可以存储 p 1 个程序 LL p i i 2 1 所以 A I OPT I 1 放的程序越多越好 所以先放小的 后放大的 放的程序越多越好 所以先放小的 后放大的 1 2 3 1 2 3 7 4 5 6 4 5 6 并不是所有 NP hard 问题都有多项式时间近似算法 最小度生成树问题 只讲什么问题 自己看吧 1 3 2 4 5 6 7 这个图的最小度生成树是什么 局部搜索算法可使所求解达到所能 达到最优解的值加 1 绝大多数问题并不存在多项式时间绝对近似算法 定理 7 2 当 P NP 时 背包问题没有多项式时间绝对近似算法 证明 背包问题的优化形式 背包优化问题 优化问题很多时候可以用整数规划形式描述 njx Bxw xp jn j jj n j jj 1 1 0 max 1 1 设背包问题存在多项式时间绝对近似算法 A 则存在常数 K 使对 背包问题的任意实例 I 有 A I OPT I K 令 p1i K 1 pi将背包问题实例变换为另一问题实例将背包问题实例变换为另一问题实例 I1 nix Bxw xp jn i ii n i ii 1 1 0 max 1 1 1 根据假设有 A I1 OPT I1 K 又有 OPT I1 K 1 OPT I 所以 可以认为 A I1 是 K 1 的整数倍 1 1 1 1 K K IOPT K IA A I1 K 1 OPT I 由于背包问题的实例中 每个元素的价值均为正整数 所以 OPT I 由此可以得到最优解值 这样货郎判定问题就可以解 1 1 A I K 决了 与 P NP 矛盾 可以假设可以假设 A I1 是是 K 1 的整数倍 的整数倍 一个问题的最优解值能知道 则其判定形式可多项式时间解答 一个问题的最优解值能知道 则其判定形式可多项式时间解答 定理 7 3 若 P NP 则最大独立集问题不存在多项式时间绝对近似 算法 证明 设最大独立集问题的实例为 G 有绝对近似算法 A 使得 A G OPT G K 构造最大独立集问题另一实例 G G 由图 G 复制 K 1 个副本组成 显然有 OPT G K 1 OPT G 对于新构造的 G 调用算法 A 得到 A G OPT G K 得到 1 1 1 K K GOPT K GA OPT G 可以求到 G 的最优解值 可以认为 A G 是 K 1 1 K GA 的倍数 所以 OPT G 与 P NP 矛盾 1 A G K 绝大多数 NP hard 问题不存在多项式时间绝对近似算法 存在绝对近似算法的问题实在太少 所以人们更多地研究如下类型存在绝对近似算法的问题实在太少 所以人们更多地研究如下类型 的算法 的算法 定义定义 7 1 最小优化问题 实例 I 解答 的近似算法 A 则算法 A 对实例 I 的近似性能比定义为 RA I 基本假设 A I OPT I IOPT IA Approximation ratio Performance ratio Performance factor 若 最大优化问题 实例 I 解答 的近似算法 A RA I 基本假设 A I OPT I IA IOPT 显然这样定义后 不论最大优化还是最小优化 近似性能比总比 1 大 近似性能比越接近 1 越说明算法好 背包问题 10 max 1 1 x BWx Px in i ii n i ii 定理 7 4 背包问题有多项式时间近似算法 任意 I 近似性能比 RA I 2 证明 设计一个算法 思想 价值重量比犹大到小排序 精打细算法 价值重量比排序精打细算法 价值重量比排序 不加思索法 直接选择不加思索法 直接选择 两者从中选优 两者从中选优 1 将 A 中的元素排序 按照性能价格比 n n w P w P w P 2 2 1 1 2 从一开始装入背包 直到不能装下为止 得到可行解 GA I 3 A I max GA I max Pi i 1 n 考虑最大价值的装法得 Pi 设正整数 r 满足 Bw r i i 1 Bw r i i 1 1 显然 a1 ar是装入背包的物体 OPT I 2 max 11 1 1 IAPPP i ni r i i r i i 所以 RA I 2 IA IOPT 装箱问题 实例 1 n 个物体的集合 S a1 an 2 每个物体 ai S 体积为 w ai 3 容量为 C 的箱子 询问 最少需要多少个箱子 才能将 S 中物体都装入箱子内 每个箱子装入物体的体积和不超过 C 首次适合算法最简单 fit first 1 设箱子为 B1 Bm 按照一定顺序将 a1 an依次装入箱 子 一个箱子装满再装另一个箱子 这就是算法 算法的时间复杂度为 O n 算法的名字叫 FF 算法的 想法就是瞎装 拿过来就装 定理 7 5 对于装箱问题的任意实例 首次适合算法的近似性能比为 RFF I 2 IOPT IFF 证明 任意两个相邻箱子 Bi 1Bi装入物体体积大于 C B1B2B3B4 Bk K FF I 若 FF I 为偶数 则 2 1 IOPTCaWC IFF n i i 两个箱子合一个 装入的东西会有富裕 两个箱子合一个 装入的东西会有富裕 所以 FF I 2OPT I 若 FF I 为奇数 2 1 1 IOPTCaWC IFF n i i FF I 2OPT I 1 因 FF I OPT I 均为正整数 所以有 FF I 2OPT I 因为是小于号 RFF I 2 IOPT IFF 到此再说明什么是绝对近似性能比 什么是渐进近似性能比 绝对近似性能比 对实例 I 的近似性能比为 RA I RA inf r 1