做app和做网站区别,北京公司请做网站工资,静态网站,建筑装饰设计培训班1、求解最优化问题的算法 通常需要经过一系列的步骤#xff0c;在每个步骤都面临多种选择。对于许多最优化问题#xff0c;使用动态规划算法求最优解有些杀鸡用牛刀了#xff0c;可以使用更简单、更高效的算法 贪心算法#xff08;greedy algorithm#xff09;就是这样的算…1、求解最优化问题的算法 通常需要经过一系列的步骤在每个步骤都面临多种选择。对于许多最优化问题使用动态规划算法求最优解有些杀鸡用牛刀了可以使用更简单、更高效的算法 贪心算法greedy algorithm就是这样的算法它在每一步都做出当时看起来最优的选择。也就是说它总是做出局部最优的选择寄希望通过这些选择导致全局最优解
2、贪心算法 并不保证得到最优解但对很多问题 确实可以求得最优解
1、活动选择问题
一个调度竞争共享资源的 多个活动的问题目标是 选出一个最大的互相兼容的活动集合。假定有一个 n 个活动的集合 S {a1, a2, …, an}这些活动使用同一资源例如一个阶梯教室每个活动 a_i 都有一个开始时间 s_i 和 一个结束时间 f_i其中 0 ≤ s_i f_i ∞。如果被选中 a_i 发生在 [si, fi) 期间。如果 a_i 和 a_j 满足 [s_i, f_i) 和 [s_j, f_j) 不重叠则称它们是兼容的 当 s_i ≥ f_j 或 s_j ≥ f_i 时a_i 和 a_j 是兼容的。希望选出一个最大兼容活动的子集
假定活动 已按结束时间的单调递增顺序排列 可以通过动态规划方法 将这个问题分为两个子问题然后 将两个子问题的最优解 结合成原问题的一个最优解。在确定该将 哪些子问题用于最优解时要考虑几种选择 贪心算法只需考虑一种选择即贪心的选择在做贪心选择时子问题之一必定是空的因此只留下一个非空子问题。找到一种递归贪心算法 来解决活动调动问题并将递归算法转化为迭代算法以完成贪心方法的过程
1.1 最优子结构
A_ij A_ij U { a_k } U A_kj而且 S_ij 中最大兼容任务子集 A_ij 包含 I A_ij I | A_ik | | A_kj l 1 个活动 用剪切一粘贴办法证明最优解 A_ij 必然包含两个子问题 S_ik 和 S_kj 的最优解
用 c[i, j] 表示集合 S_ij 的最优解的大小
1.2 贪心选择
假如 发现所有子问题都可以选择出一个活动加入到最优解对于活动选择问题 只需要考虑一个选择贪心选择
应该选择这样一个活动选出它后 剩下的资源应能被尽量多的其他任务所用。现在考虑可选的活动 其中必然有一个最先结束。应该选择S中最早结束的活动因为 它剩下的资源可供它之后尽量多的活动使用
选择最早结束的活动并不是本问题唯一的贪心选择方法也可以选择 最晚开始活动开始要把 活动开始时间 从晚到早排序贪心 之前的排序很重要然后把满足条件的顺次加入进去 就行
定理16.1 考虑任意非空子问题s且 a_j 是 A_k 中结束时间最早的活动则 a_m 在 S_k 的某个最大兼容子集中 虽然 可以用动态规划方法 求解活动选择问题但并不需要这样做此外并未检查活动选择问题 是否具有重叠子问题性质。相反可以反复选择 最早结束的活动保留与此活动兼容的活动重复这一过程直至无剩余活动可选 而且因为 总是选择最早结束的活动所以选择的活动 在结束时间上总是严格递增的只需要 按结束时间的单调递增顺序 去处理所有活动每个活动只考虑一次
贪心算法 通常都是这种自顶向下的设计做出一个选择然后求解剩下的那个子问题
1.3 递归贪心算法
输入为两个数组 s 和 f表示活动的开始 和 结束时间下标 k 指出要求解的子问题 S_k, 以及 问题规模 n
为了方便 算法初始化添加一个虚拟活动 a_0其结束时间 f_0 0因为上来的活动就是 k 1求解原问题 即可调用RECURSIVE-ACTIVITY-SELECTOR(s, f, 0, n)
RECURSIVE-ACTIVITY-SELECTOR(s, f, k, n)
1 m k 1
2 while m n and s[m] f[k]
3 m m 1
4 if m n
5 return {a_m} ∪ RECURSIVE-ACTIVITY-SELECTOR(s, f, m, n) // 下一代从 k m 开始
6 else return ∅可能因为 mn 而终止这意味着我们已经检查了 S_k 中所有活动未找到与 a_k 兼容者
假定活动 已经按结束时间排好序则递归调用 RECURSIVE-ACTIVITY-SELECTOR(s, f, 0, n) 的运行时间为 Θ(n)在整个递归调用过程中每个活动只被 while 循环检查一次
1.4 迭代贪心算法
1、将算法转换为 迭代形式。过程 RECURSIVE-ACTIVITY-SELECTOR 几乎就是“尾递归”。它以一个对自身的递归调用 再接一次并集操作结尾。将一个尾递归过程 改为 迭代形式 通常是很直接的实际上某些特定语言的编译器可以自动完成这一工作
GREEDY-ACTIVITY-SELECTOR(s, f)
1. n s.length
2. A {a_1}
3. k 1
4. for m 2 to n
5. if s[m] f[k]
6. A A ∪ {a_m}
7. k m
8. return A与递归版本类似在输入活动已按结束时间排序的前提下GREEDY-ACTIVITY-SELECTOR 的运行时间为 Θ(n)
2、并不是所有贪心方法都能得到最大兼容活动子集。在剩余兼容活动中 选择 持续时间最短者 不能得到最大集。在剩余兼容活动选择与其他剩余活动重叠最少者 也是同理
3、假定有一组活动需要将它们安排到一些教室任意活动都可以在任意教室进行。希望使用最少的教室完成所有活动。设计一个高效的贪心算法来安排哪些活动在哪个教室进行
(这个问题称为 区间图着色问题(interval-graph coloring problem))。可以构建一个区间图其中表示活动的节点边连接不兼容的活动。要求用最少的颜色对图的顶点进行着色使用所有邻项顶点之间的不同颜色 这个算法的关键在于贪心策略 总是优先使用已经空闲的讲堂来安排新的活动 只有当没有空闲讲堂时才添加新的讲堂 不能用贪心了O(n3) 是 i 从0到 nj 从 i 1 到 nk 从 i 到 j 因为 c[i, k] c[k, j] V_k 希望最大化兼容活动的总价值可以使用动态规划Dynamic Programming, DP来实现
def find_latest_non_conflicting(activities, n):for j in range(n-1, -1, -1):if activities[j][1] activities[n][0]:return jreturn -1def activity_selection_with_values(activities):# 按结束时间排序activities.sort(keylambda x: x[1])# 动态规划数组n len(activities)dp [0] * (n 1)for i in range(1, n 1):# 当前活动的值value activities[i-1][2]# 查找最新的与当前活动兼容的活动j find_latest_non_conflicting(activities, i-1)# 递推公式if j ! -1:dp[i] max(dp[i-1], value dp[j1])else:dp[i] max(dp[i-1], value)return dp[n]# 示例活动 (开始时间, 结束时间, 价值)
activities [(1, 3, 5), (2, 5, 6), (4, 6, 5), (6, 7, 4), (5, 8, 11), (7, 9, 2)]
print(最大价值, activity_selection_with_values(activities))
2、贪心算法原理
1、通过 做出一系列选择来求出问题的最优解。在每个决策点它做出在当时看来最佳的选择。这种 启发式策略 并不保证总能找到全局最优解
2、设计贪心算法步骤
将最优化问题 转换为这样的形式对其做出一次选择后只剩下一个子问题需要求解证明做出贪心选择后原问题总是 存在最优解即贪心选择是安全的证明做出贪心选择后剩余的子问题 满足性质其最优解与贪心选择组合 即可得到原问题的最优解这样就得到了最优子结构
2.1 贪心选择性质
1、可以通过做出局部最优贪心选择 来构建全局最优解
2、与动态规划 先求解子问题才能 进行第一次选择不同贪心算法 在进行第一次选择之前 不求解任何子问题一个动态规划算法是 自底向上 进行计算的而一个贪心算法 通常是自顶向下的进行一次又一次选择将给定问题实例 变得更小
3、必须证明每个步骤 做出贪心选择 能生成全局最优解。这种证明 通常首先考查 某个子问题的最优解然后用贪心选择 替换某个其他选择 来修改此解从而得到一个相似但更小的子问题
进行贪心选择时 不得不考虑 众多选择通常意味着 可以改进贪心选择使其更为高效 例如在活动选择问题中假定 已经将活动按结束时间单调递增顺序 排好序则对每个活动能够只处理一次。通过对输入进行预处理 或者 使用适合的数据结构通常是优先队列通常可以使得贪心选择更快速从而得到更有效的算法
2.2 最优子结构
1、如果一个问题的最优解 包含其子问题的最优解则称此问题具有 最优子结构性质。此性质是 能否应用动态规划 和 贪心算法的关键要素
活动选择问题为例如果一个子问题 S_ij 的最优解包含活动a_k那么必然也包含子问题 S_ik 和 S_kj 的最优解 如果知道 S_ij 的最优解应该包含 哪个活动 a_k就可以组合 a_k 以及 S_ik 和 S_kj 的最优解中所有活动来构造 S_ij 的最优解
2、论证最优子结构将子问题的最优解 与 贪心选择 组合在一起就能生成原问题的最优解。这种方法隐含对于子问题 使用了数学归纳法证明了 每个步骤进行贪心选择都会生成原问题的最优解
2.3 贪心对动态规划
1、0-1背包问题一个正在抢劫商店的小偷 发现了 n 个商品第 i 个商品价值 v_i 美元重 w_i 磅v_i 和 w_i 都是整数。小偷希望 拿走价值尽货高的商品但他的背包 最多能容纳 W 磅重的商品 W是一个整数。应该拿哪些商品 称这个问题是 0-1 背包问题 因为对每个商品小偷要么把它完整拿走 要么把它留下不能只拿走一部分
2、在分数背包问题 中设定与 0-1 背包问题是一样的不同的是小偷可以拿走其一部分而不是 只能做出二元 (0-1) 选择
3、两个背包问题都具有 最优子结构性质。对0-1背包问题考虑重量不超过 W 而 价值最高的装包方案。如果 将商品 j 从此方案中删除则剩余商品 必须是重量不超过 W - w_j 的价值最高的方案
贪心策略 可以求解分数背包问题而不能求解 0-1 背包问题 为了求解分数背包问题首先计算每个商品的每磅价值 v_i / w_i 。遵循贪心策略首先尽量多地拿 每磅价值最高的商品。通过将背包按每磅价值排序贪心算法的运行时间可为 O(nlgn)
证明分数背包问题具有贪心选择性质
拿走商品 1 的策略对 0-1 背包问题无效 是因为小偷无法装满背包空闲空间降低了方案的有效每磅价值。在 0-1 背包问题中当考虑是否 将一个商品装入背包时必须比较包含 此商品的子问题的解 与 不包含它的子问题的解然后才能做出选择。这会导致大量的重叠子问题——动态规划的标识
设计动态规划算法求解 0-1 背包问题要求运行时间为 O(nW)n 为商品数量W 是小偷能放进背包中的最大商品总重量 动规不用事先排序 K含义K[考虑过的物品 剩余空间重量]
0-1-KNAPSACK(n, W)Initialize an (n 1) by (W 1) table Kfor i 1 to nK[i, 0] 0for j 1 to WK[0, j] 0for i 1 to nfor j 1 to Wif j i.weightK[i, j] K[i - 1, j]elseK[i, j] max(K[i - 1, j], K[i - 1, j - i.weight] i.value)3、赫夫曼编码
1、根据每个字符的出现频率赫夫曼算法 构造出字符的最优二进制表示 每个字符用一个唯一的一二进制串表示称为码字。如果使用定长编码需要用3位表示6个字符a000, b001, …, f101。这种方法需要300,000个二进制位来编码文件
2、变长编码 可以达到 比定长编码好得多的压缩率其思想是赋予高频字符 短码字赋予低频字符 长码字。上图显示了六个字符的一种变长编码1位的a表示4位的f表示。因此这种编码表示此文件 (45⋅113⋅312⋅316⋅39⋅45⋅4)⋅1000224,000位 与定长编码相比 节约了25%的空间这是 此文件的最优字符编码
3.1 前缀码
1、只考虑所谓前缀码即没有任何字符是其他字符的前缀。与任何字符编码相比前缀码 都可以保证达到最优数据压缩率。因此 只关注前缀码不会丧失一般性
前缀码的作用是 简化解码过程。由于没有码字是其他码字的前缀编码文件的开始码字是无歧义的。可以简单地识别出 开始码字将其转换回 原字符然后对编码文件剩余部分 重复这种解码过程
在上节的例子中二进制串 001011101 可以唯一地解析为 0·0·101·1101解码为 aabec
2、解码过程 需要前缀码的一种方便的表示形式以便 可以容易地截取开始字符。一种二叉树表示 可以满足这种需求其叶结点为 给定的字符。字符的二进制码字 用从根结点到该字符叶结点的简单路径表示其中 0 意味着 “转向左孩子”1 意味着 “转向右孩子” 注意编码树并不是二叉搜索树因为叶节点并未有序排列而内部结构并不包含 字符关键字 文件的最优编码方案总是对应一棵 满(full) 二叉树即每个非叶节点都有两个孩子结点。前文给出的定长编码实例 不是最优的因为它的二叉树表示 并非 满二叉树 若 C 为字母表 且 所有字符的出现频率 均为正数则最优编码树对应的树结构恰有 |C| 个叶结点每个叶结点对应字母表中一个字符且恰有 |C|−1 个内部结点
对字母表C中的每个字符c令属性 c.freq 表示 c 在文件中出现的频率令 d_T(c) 表示c的叶结点在树中的深度。注意d_T(c) 也是字母c的码字的长度。则编码该文件需要
3.2 构造赫夫曼编码
1、贪心算法来构造最优前缀码它的正确性证明 依赖于 贪心选择性质 和 最优子结构
2、算法自底向上地构建出 对应最优编码的二叉树 T 它从 |C| 个叶结点开始执行 |C|−1 次“合并”操作 创建出最终的二叉树。算法使用一个以 属性 freq 为关键字的最小优先队列 Q以识别 两个最低频率的对象 将其合并。当合并两个对象时得到的新对象的频率 等于原来两个对象频率之和 根 搜索树不一样没有其他对节点的顺序限制之后只需要 让频率大的靠近根频率小的远离根
HUFFMAN(C)
1 n |C|
2 Q C
3 for i 1 to n-1
4 allocate a new node z
5 z.left x EXTRACT-MIN(Q) // 把代价最小的删除并返回
6 z.right y EXTRACT-MIN(Q)
7 z.freq x.freq y.freq
8 INSERT(Q, z)
9 return EXTRACT-MIN(Q) // return the root of the tree由于字母表 包含6个字符初始队列大小为 n6 for循环 反复从队列中提取两个频率最低的结点 x 和 y将它们合并为 一个新结点z替代它们。z的频率为 x 和 y 的频率之和 结点z将 x 作为其左孩子将 y 作为其右孩子顺序是不重要的交换左右孩子会生成一种不同的编码但代价完全一样。经过 n−1 次合并后第9行返回队列中剩下的唯一结点——编码树的根结点
3、为了分析赫夫曼算法的运行时间假定 Q 是使用最小二叉堆实现的参见第6章。在第2行用 BUILD-MIN-HEAP过程参见6.3节将 Q 初始化花费时间为 O(n)。第38行的 for 循环执行 n−1 次且每个堆操作需要 O(lgn) 的时间所以循环对总时间的贡献为 O(nlgn)。因此处理一个n个字符的集合HUFFMAN 的总运行时间为 O(nlgn)
3.3 赫夫曼算法的正确性
1、确定最优前缀码的问题 具有贪心选择 和 最优子结构性质
2、1令 C 为一个字符表其中每个字符 c∈C 都有一个频率 c.freq。令 x 和 y 是 C 中频率最低的两个字符。那么存在 C 的一个最优前缀码x 和 y 的码字长度相同且 只有最后一个二进制位不同即是 兄弟结点在最优的基础上 每次合并仍是最优即可合并
证明 证明的思想是令 T 表示任意一棵最优前缀码所对应的编码树对其进行修改得到表示另外一个最优前缀码的编码树使得在新树中x 和 y 是深度最大的叶结点且它们为兄弟结点 如果 可以构造这样一棵树那么 x 和 y 的码字将有相同长度且只有最后一位不同
令 a 和 b 是 T 中深度最大的兄弟叶结点 不失一般性 假定a.freq b.freq 且 x.freq y.freq。由于 x.freq 和 y.freq 是叶结点中最低的两个频率而 a.freq 和 b.freq 是两个任意频率。因此 我们有 x.freq a.freq 且 y.freq b.freq 交换 x 和 a 生成一棵新树 T’, 井在 T 中交换 b 和 y 生成一棵新树 T T和T’的代价差为 类似地交换 x 和 b 也不能增加代价所以 B(T′) − B(T’‘) 也是非负的。因此 B(T′′) B(T)由于 T 是最优的我们有 B(T′’) B(T)这意味着 B(T′′) B(T)。因此T’’ 也是最优树且 x 和 y 是其中深度最深的兄弟结点引理成立 3、通过合并来构造最优树的过程可以 从合并出现频率最低的两个字符 这样一个贪心选择开始。为什么这是一个贪心选择可以将每一次合并操作的代价 看做 被合并的两项的频率之和
在每个步骤 可选择的所有合并操作中HUFFMAN 选择是 代价最小的那个下面的引理证明了构造最优前缀码的问题具有最优子结构性质
2令 C 为一个含有 n 个字符表其中每个字符 c∈C 都有一个频率 c.freq。令 C’ 为 C 去棹字符 x 和 y, 加入一个新字符 z 后得到的宇母表即 C’ C - {x, y} ∪{z}z.freq x.freq y.freq。令 T’ 为字母表 C’ 的任意一个最优前缀码对应的编码树。于是 可以将 T’ 中叶结点 z 替换为一个以 x 和 y 为孩子的内部结点得到树 T, 而 T 表示字母表C的 一个最优前缀码
证明用树 T’ 的代价 B(T’) 来表示树 T 的代价 B(T) 用反证法来证明引理。假定 T 对应的前缀码并不是 C 的最优前缀码存在最优编码树 T’’ 满足 B(T′‘) B(T)。不失一般性(由引理 16.2)T’’ 包含兄弟结点 x 和 y令 T’’ 将 T 中 x,y 及它们的父结点替换为叶结点 z 得到的树其中 z.freq x.freq y.freqT’‘’ 对应 T’T’’ 对应 T 与 T’ 对应 C’ 的一个最优前缀码的假设矛盾。因此 T 必然表示字符表 C 的一个最优前缀码即最优 T 一定包含 最优 T’最优子结构
4、由12过程 HUFFMAN 会生成一个最优前缀码 5、
