贪心算法46284

1 第4章贪心算法 找钱问题 要找给顾客3角7分钱硬币面值为1角 5分 2分 1分 贪心算法 1角 3枚 5分 1枚 2分 1枚合计 5枚能得到最优解面值为11分 7分 5分 1分 贪心算法 11分 3枚 1分 4枚合计 7枚但最优解应该是5枚 贪心法不成功 贪心算法概述 在贪婪算法中采用逐步构造最优解的方法 在每个阶段 都作出一个看上去最优的决策它并不一定对所有问题都成功 但是对某些问题特别简单 有效 决策一旦作出 就不可再更改 作出贪婪决策的依据称为贪婪准则 criterion 对一些NP完全问题或规模很大的优化问题 可通过仿贪心算法能得到很好的近世解 而用动态规划根本无法解 4 4 1活动安排问题 设有n个活动的集合E 1 2 n 其中每个活动都要求使用同一资源 如演讲会场等 而在同一时间内只有一个活动能使用这一资源每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi 且si fi如果选择了活动i 则它在半开时间区间 si fi 内占用资源若区间 si fi 与区间 sj fj 不相交 则称活动i与活动j是相容的也就是说 当si fj或sj fi时 活动i与活动j相容 5 4 1活动安排问题 例 设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下 6 4 1活动安排问题 算法greedySelector的计算过程如左图所示 图中每行相应于算法的一次迭代 阴影长条表示的活动是已选入集合A的活动 而空白长条表示的活动是当前正在检查相容性的活动 7 4 1活动安排问题 在下面所给出的解活动安排问题的贪心算法greedySelector publicstaticintgreedySelector int s int f booleana intn s length a 1 true intj 1 intcount 1 for inti 2 i f j a i true j i count elsea i false returncount 各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列 8 4 1活动安排问题 由于输入的活动以其完成时间的非减序排列 所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中 直观上 按这种方法选择相容活动为未安排活动留下尽可能多的时间 也就是说 该算法的贪心选择的意义是使剩余的可安排时间段极大化 以便安排尽可能多的相容活动 算法greedySelector的效率极高 当输入的活动已按结束时间的非减序排列 算法只需O n 的时间安排n个活动 使最多的活动能相容地使用公共资源 如果所给出的活动未按非减序排列 可以用O nlogn 的时间重排 9 4 2贪心算法的特点 所求问题的整体最优解可以通过一系列局部最优的选择 即贪心选择来达到 动态规划算法通常以自底向上的方式解各子问题 而贪心算法则通常以自顶向下的方式进行 以迭代的方式作出相继的贪心选择 每作一次贪心选择就将所求问题简化为规模更小的子问题 10 4 2贪心算法 0 1背包问题 给定n种物品和一个背包 物品i的重量是Wi 其价值为Vi 背包的容量为C 应如何选择装入背包的物品 使得装入背包中物品的总价值最大 在选择装入背包的物品时 对每种物品i只有2种选择 即装入背包或不装入背包 不能将物品i装入背包多次 也不能只装入部分的物品i 11 4 2贪心算法 背包问题 背包问题 与0 1背包问题类似 所不同的是在选择物品i装入背包时 可以选择物品i的一部分 而不一定要全部装入背包 1 i n 这2类问题都具有最优子结构性质 极为相似 但背包问题可以用贪心算法求解 而0 1背包问题却不能用贪心算法求解 至少有三种看似合理的贪心策略 1 选择价值最大的物品 因为这可以尽可能快地增加背包的总价值 但是 虽然每一步选择获得了背包价值的极大增长 但背包容量却可能消耗得太快 使得装入背包的物品个数减少 从而不能保证目标函数达到最大 2 选择重量最轻的物品 因为这可以装入尽可能多的物品 从而增加背包的总价值 但是 虽然每一步选择使背包的容量消耗得慢了 但背包的价值却没能保证迅速增长 从而不能保证目标函数达到最大 3 选择单位重量价值最大的物品 在背包价值增长和背包容量消耗两者之间寻找平衡 12050背包180190200 a 三个物品及背包 b 贪心策略1 c 贪心策略2 d 贪心策略3 例如 有3个物品 其重量分别是 20 30 10 价值分别为 60 120 50 背包的容量为50 应用三种贪心策略装入背包的物品和获得的价值如图所示 voidKnapsack intn floatM floatv floatw floatx Sort n v w 按单位价值排序 inti for i 1 ic break x i 1 c w i if i n x i c w i 算法分析 排序为主要算法时间 所以T n O nlogn 背包问题的贪心算法 背包问题中的物体不能分拆 只能整个装入称为0 1背包问题 算法证明 该算法能得到在最优解 用贪心算法能得到0 1背包的最优解吗 0 1背包问题的几种贪婪策略 1 从剩余的物品中 选出可以装入背包的价值最大的物品2 从剩下的物品中选择可装入背包的重量最小的物品3 从剩余物品中选择可装入包的pi wi值最大的物品这三种策略都不能保证得到最优解 0 1背包问题是一个NP复杂问题 对于这类问题 也许根本就不可能找到具有多项式时间的算法 为什么贪心策略不适用于0 1背包问题 例 c 50 w 10 20 30 V 60 100 120 单价v w 6 5 4 按贪心策略 应装入前两个物品 价值160 最优解应为装入后两种物品 价值220 原因 贪心法不能保证0 1背包装满 闲置部分使背包价值降低 考虑0 1背包问题 应比较选择wi与不选择wi所导致的结果 然后作出选择 由此导致相互重叠的子问题 所以可用动态规划法 虽然按pi wi非递增的次序装入物品不能保证得到最优解 但它是一个直觉上近似的解 我们希望它是一个好的启发式算法 且大多数时候能很好地接近最后算法 据统计 在600个随机产生的背包问题中 用这种启发式贪婪算法来解有239题为最优解 有583个例子与最优解相差10 所有600个答案与最优解之差全在25 以内 该算法能在O nlogn 时间内获得如此好的性能 18 4 3最优装载 有一批集装箱要装上一艘载重量为c的轮船 其中集装箱i的重量为Wi 最优装载问题要求确定在装载体积不受限制的情况下 将尽可能多的集装箱装上轮船 1 算法描述最优装载问题可用贪心算法求解 采用重量最轻者先装的贪心选择策略 可产生最优装载问题的最优解 具体算法描述如下页 19 例 设n 8 w1 w8 100 200 50 90 150 50 20 80 c 400 算法思路 将装船过程划为多步选择 每步装一个货箱 每次从剩下的货箱中选择重量最轻的货箱 如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱 所考察货箱的次序为 7 3 6 8 4 1 5 2 货箱7 3 6 8 4 1的总重量为390个单位且已被装载 剩下的装载能力为10 小于任意货箱 所以得到解 x1 x8 1 0 1 1 0 1 1 1 20 最优装载的贪心算法 templatevoidLoading intx Typew Typec intn int t newint n 1 Sort w t n 按货箱重量排序 for inti 1 i n i x i 0 for inti 1 i n 调整剩余空间 算法分析 排序为主要算法时间 所以T n O nlogn 算法证明 该算法能得到最优解 21 4 4Huffman编码 Huffman编码用于数据压缩例 字符出现频率与编码方案abcdef频率4513121695定长码000001010011100101变长码10100011011变长码2010110011111011100但是变长码1的识别困难 因为不具有前缀性质 22 变长码2属于前缀码 即任何一个字符的编码都不是其它字符编码的前缀 这样能保证译码迅速 唯一确定 例 001011101 001011101 aabe前缀码的二叉树表示树叶 字符前缀码 树根到树叶的路径例 变长码2对应的二叉树 100 55 25 30 a 45 14 f 5 d 16 b 13 c 12 e 9 0 1 0 0 0 0 1 1 1 23 对应前缀码的二叉树为完全二叉树 即每个结点有两个儿子 n个字符对应n个叶结点 n 1个内部结点 设字符c在文件中出现频率为f c 其前缀码编码方案对应一棵二叉树 字符c在树中的深度为d c 则编码的平均码长为 B T f c d c 平均码长最小的方案为最优前缀码Huffman编码是一种最优前缀码 可用贪心算法构造此编码 24 构造过程 以 c 个叶结点开始 执行 c 1次 合并 运算 最后生成T 字符c的频率为f c 队列Q以f c 为键值存放二叉树各结点 通过贪心选择 将最小频率的两个二叉树合并 然后将新树 频率为上述两个二叉树频率之和 插入Q中 24 25 设在1000个字母的文章中各字母出现的频率为 a 83 b 14 c 28 d 38 e 131 f 29 g 20 h 53 14202829385383131 342829385383131 3457385383131 57725383131 7211083131 110155131 155241 396 396 155 241 110 131 53 57 72 83 34 38 28 29 14 20 1 0 1 0 1 0 1 0 1 0 1 0 1 0 最佳编码 a 10 b 1111 c 0101 d 110 e 00 f 0100 g 1110 h 011 1 将权从小到大排序2 每次选取最小权合并 例题 算法设计与分析 贪心算法 哈夫曼编码 26 templateBinaryTreeHuffmanTree Tf intn 根据权f 1 n 构造霍夫曼树 创建一个单节点树的数组Huffman W newHuffman n 1 BinaryTreez zero for inti 1 i Q 1 Q Initialize w n n 将堆中的树不断合并Huffmanx yfor i 1 i n i Q DeleteMin x Q DeleteMin y z MakeTree 0 x tree y tree x weight y weight x tree z Q Insert x Q DeleteMin x 最后的树Q Deactivate delete w returnx tree 霍夫曼树算法 27 4 4哈夫曼编码 在书上给出的算法huffmanTree中 编码字符集中每一字符c的频率是f c 以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树 一旦2棵具有最小频率的树合并后 产生一棵新的树 其频率为合并的2棵树的频率之和 并将新树插入优先队列Q 经过n 1次的合并后 优先队列中只剩下一棵树 即所要求的树T 算法huffmanTree用最小堆实现优先队列Q 初始化优先队列需要O n 计算时间 由于最小堆的DeleteMin和Insert运算均需O logn 时间 n 1次的合并总共需要O nlogn 计算时间 因此 关于n个字符的哈夫曼算法的计算时间为O nlogn 28 时间复杂度 用f c 初始化对列Q的时间 O n DeleteMin Insert需要时间 O logn n 1次合并需要时间 O nlogn 29 4 5单源最短路径问题 有向图G的每条边都有一个非负的长度c i j 路径的长度即为此路径所经过的边的长度之和 例 具有五个顶点的有向图 各边上的数即为长度 对于给定源顶点v1 需找出从它到图中其他任意顶点的最短路径 30 E Dijkstra的贪婪算法通过分步方法求出最短路径 每一步产生一个到达新的目的顶点的最短路径 下一步所能达到的目的顶点通过如下贪婪准则选取 在还未产生最短路径的顶点中 选择路径长度最短的目的顶点 即按路径长度顺序产生最短路径 最初产生从v到它自身的路径 这条路径没有边 其长度为0 在贪婪算法的每一步中 产生下一个最短路径 31 设u是图中某个顶点 将从源点v到u且中间只经过S中顶点的路径称为从源点v到u的特殊路径 用dist u 来记录从源点v到u的特殊路径长度 每次从V S中寻找dist u 最小的u 将u从V S中去掉 加入S中 u加入S可能导致dist j 减少 j V S 这是由于新增的路径 v u j 有可能比原路径 v j 短 故用dist u c u j 取代原来的dist j S v u1 u2 V S 用贪心选择来扩充集合S 起初 S中仅包含源点v 某顶点u S 从源点v到u的最短路径已知 32 算法设计与分析 贪心算法 算法描述 1 用带权的邻接矩阵c来表示带权有向图 c i j 表示弧上的权值 若 V 则置c i j 为 设S为已知最短路径的终点的集合 它的初始状态为 v 从源点v到图上其余各点vi的当前最短路径长度的初值为 dist i c v i vi V S 2 选择vj 使得dist j Min dist i vi V S vj就是长度最短的最短路径的终点 令S SU j 3 修改从v到集合V S上任一顶点vk的当前最短路径长度 如果dist j c j k dist k 则修改dist k dist j c j k 4 重复操作 2 3 共n 1次 33 算法设计与分析 贪心算法 单源最短路径 例题 1 v1 v2 10 2 v1 v3 50 3 v1 v4 30 4 v1 v5 60 34 算法设计与分析 贪心算法 voidDijkstra intn intv Typedist intprev Type c bools maxint for inti 1 i n i dist i c v i s i false if dist i maxint prev i 0 elseprev i v dist v 0 s v true for inti 1 i n i inttemp maxint intu v for intj 1 j n j if s j 单源最短路径问题的Dijkstra算法 分析 用带权邻接矩阵表示有n个顶点和e条边的带权有向图 主循环体需要O n 时间 循环需要执行n 1次 所以完成循环需要O n2 35 算法说明 S i false 表示顶点i不在S集合中开始 只有S v truePrev i 存放顶点i的前驱结点 即从源点到顶点i的最短路径上i的前一个结点 当dist u c u i dist i 时 Prev i u根据Prev的值 产生最短路径 例 Prev 2 1 Prev 3 4 Prev 4 1 Prev 5 3顶点1到顶点5的路径 1 4 3 5 1 2 3 4 5 36 计算复杂性 对于具有n个顶点和e条边的带权有向图 如果用带权邻接矩阵表示这个图 那么Dijkstra算法的主循环体需要时间 这个循环需要执行n 1次 所以完成循环需要时间 算法的其余部分所需要时间不超过 37 4 6最小生成树 图G V E 是无向连通带权图 即一个网络 若子图G 包含G的全部顶点 则称G 为G的生成树 生成树上各边的权之和称为生成树的耗费 耗费最小的生成树叫最小生成树 最小的生成树在通信网络 电路设计中应用广泛 贪心算法可用于构造最小生成树 Prim算法或Kruskal算法 38 算法设计与分析 贪心算法 最小生成树 问题陈述 设G V E 是一个无向连通带权图 E中每条边 v w 的权为c v w 若G的一个子图G 是一棵包含G的所有顶点的树 则称G 为G的生成树 生成树各边权的总和称为该生成树的耗费 在G的所有生成树中 耗费最小的生成树称为G的最小生成树 抽象描述 输入 任一连通生成子图 该子图的边集合 可行解 图的生成树 优化函数 生成树的各边权值之和最优解 使优化函数达到最小的生成树 4 6最小生成树 39 最小生成树性质 设G V E 是连通带权图 U是V的真子集 若 u v E u U v V U 且在所有这样的边中 u v 的权c u v 最小 那么一定存在G的一棵最小生成树包含边 u v U V U u u v v 40 算法思路 首先置S 1 T 若S V 就作如下的贪心选择 选取满足条件i S j V S 且c i j 最小的边 i j 将顶点j添加到S中边 i j 添加到T中 这个过程一直进行到S V时为止 T中的所有边构成G的一棵最小生成树 voidPrim intn Type c T S 1 while S V i j i S且j V S的最小权边 T TU i j S SU j 算法描述 Prim算法 设G V E 是一个连通带权图 y l 2 n 例题 算法设计与分析 贪心算法 最小生成树 41 例题 算法设计与分析 贪心算法 最小生成树 42 算法说明 T中最后包含n 1条边 时间复杂度O n2 为了找出满足i S j V S且c i j 最小的边 i j 设置两个数组 closest和Lowcostclosest j 表示j j V S 在S中一个邻接顶点 并且c j closest j c j k k是j在S中的其它邻接顶点Lowcost j c j closest j 43 TemplateVoidPrim intn Type c Typelowcost maxint intclosest maxint bools maxint s 1 true for inti 2 i n i lowcost i c 1 i closest i 1 s i false for inti 1 i n k n 1条边 Typemin inf intj 1 for intk 2 k n k 每次从V S中选使lowcost距离最小的点jif lowcost k min s j true j加入S后 引起lowcost的变化for intk 2 k n k if c j k lowcost k 44 Kruskal算法 假设有n个顶点 e条边 1 将图G的n个顶点看作n个孤立的连通分支2 将边按权值从小到大排列3 在不构成环路的情况下 依次选取权值最小的边 直到有n 1条边为止 当查看第k条边 v w 时 若v和w属于两个不同的连通分支T1和T2 就用边 v w 将T1和T2连成一个连通分支 并继续处理第k 1条边 若v和w属于同一个连通分支 则直接查看第k 1条边 45 例题 算法设计与分析 贪心算法 最小生成树 46 templateboolKruskal intn inte EdgeNodeE EdgeNodet MinHeap H 1 H initialize E e e UnionFindU n intk 0 while e e inta U Find x u intb U Eind x v a b 表同一连通分支if a b t k x U Union a b H Deactivate renturn k n 1 Kruska算法 e1 1 e2 6 e8 9 e6 2 e9 4 e5 5 e4 7 e10 8 e11 3 e7 10 e3 11 1 以G中全部点为点作图 2 按权的大小次序依次添加各边 若出现回路则忽略此边 3 加入n 1条边后就得到最小生成树 1 2 5 3 7 求最小生成树 Kruscal 最优解 e1 e6 e11 e5 e4 48 按权的递增顺序查看等价于对优先队列执行removeMin运算 可以用堆实现这个优先队列 Kruskal算法的时间复杂度为O eloge Prim算法或Kruskal算法的比较两个算法的时间复杂度分别为O n2 和O eloge 当图的边数较少时 Kruskal算法优于Prim算法 当图的边数较多时 用Prim算法为好 49 4 7多机调度问题 N个独立的作