第4章 贪心算法46188

第4章贪心算法 4 1什么是贪心法4 2贪心法的典型示例本章小结 4 1什么是贪心法 4 1 1复杂问题的求解方法4 1 2贪心法的设计思想4 2 3几个例子4 2 4小结 4 1 1复杂问题的求解典型方法 分治法将复杂问题分成若干个相互独立的子问题 通过求解子问题 并将子问题的解合并得到原问题的解 动态规划法将一个复杂问题分解为若干个相互重叠的子问题 通过求解子问题形成一系列决策得到原问题的解 动态规划是对分治的改善 在发现有重叠问题时 使用自底向上的策略避免重复计算 从而提升了算法的效率 但仅有动态规划是不够的 4 1 1复杂问题的求解典型方法 贪心法 GreedyMethod 将一个复杂问题分解为一系列较为简单的局部最优选择 每一个选择都是对当前解的一个扩展 直到获得问题的完整解 搜索法 4 1 2贪心法的设计思想 基本思想将问题的求解过程看作是一系列选择 每次选择都是当前状态下的最好选择 局部最优解 每作一次选择后 所求问题会简化为一个规模更小的子问题 从而通过每一步的最优解逐步达到整体的最优解 4 1 2贪心法的设计思想 特点贪心法在解决问题的策略上目光短浅 只根据当前已有的信息就做出选择 而且一旦做出了选择 不管将来有什么结果 这个选择都不会改变 换言之 贪心法并不是从整体最优考虑 它所做出的选择只是在某种意义上的局部最优 4 2 3几个例子 例1 数字三角形问题例2 渴婴问题例3 找零钱问题 例1 数字三角形问题 数字三角形问题穷举法动态规划法89 13 11 26 15 24贪心法63 13 11 12 14 13 例2 渴婴问题 问题描述已知 饮料类型 n饮料满意度 s1 s2 si sn饮料总量 a1 a2 ai an需求 t问 需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求 而且能达到最大的满意程度呢 例2 渴婴问题 问题分析 令 xi为婴儿将要饮用的第i种饮料的量则 需要解决的问题是找到一组实数xi 1 i n 例2 渴婴问题 解决方案 分步获取饮料 每次喝一种饮料 且需要考虑选用哪种饮料 根据这种思想 利用如下的贪心准则 从余下的饮料中 选择满意度最高的饮料 直到达到解渴的需要 或者全部饮料被喝完为止 例3 找零钱问题 问题描述假如售货员需要找给小孩98元的零钱 售货员手中有1 2 5 10 20 50元的零钱若干 在小孩的催促下 售货员想尽快将钱找给小孩 分析 贪心准则 每一次选择应使零钱数尽量增大 为保证解法的可行性 即 所给的零钱数等于要找的零钱 每次所选择的硬币不应使零钱总数超过最终所需的数目 具体做法 98 50 20 20 5 2 1 4 1 4小结 思想由一系列步骤构成每步满足可行 满足问题的约束条件局部最优 当前状况下的最优解不可取消 一旦作出选择 不可更改求解问题的类型局部最优导致全局最优 最优解 局部最优接近全局最优 近似解 但速度极快优点求解速度快 时间复杂性有较低的阶 4 1 4小结 贪心法的基本要素 具备贪心选择性质和最优子结构性质的最优化问题 整体的最优解可通过一系列局部最优解达到 每次的选择可以依赖以前作出的选择 但不能依赖于后面的选择 问题的整体最优解中包含着它的子问题的最优解 4 2贪心法的典型应用 组合问题中的贪心法图问题中的贪心法其他问题 应用专题一 组合问题中的贪心法例1 活动安排问题例2 最优装载问题例3 0 1背包问题例4 背包问题贪心法与动态规划法的异同点例5 多机调度问题 例1 活动安排问题 问题提出 n个活动的集合E 1 2 n 每个活动i要求使用资源的时间 si fi 活动i与活动j是相容的 若区间 si fi 与区间 sj fj 不相交 称活动i与活动j是相容的 活动安排问题 在所给的活动集合中选出最大的相容活动子集合 即 要求高效地安排一系列争用某一公共资源的活动 例1 活动安排问题 分析 安排活动时应该将结束时间早的活动尽量往前安排 好给后面的活动安排留出更多的时间 从而达到安排最多活动的目标 贪心准则在未安排的活动中挑选结束时间最早的活动安排 将各项活动的开始时间和结束时间分别用两个数组s和f存储 并使得数组中元素的顺序按结束时间非减排列 f1 f2 fn 例1 活动安排问题 例如 1234567891011 2 4 5 6 1 3 7 例1 活动安排问题 算法描述 intgreedySelector ints intf boola a 1 true intj 1 count 1 for inti 2 i f j a i true j i count elsea i false returncount 例1 活动安排问题 算法时间分析 算法greedySelector的效率极高 当输入的活动已按结束时间的非减序排列 算法只需O n 的时间安排n个活动 使最多的活动能相容地使用公共资源 如果所给出的活动未按非减序排列 可以用O nlogn 的时间重排 例1 活动安排问题 利用数学归纳法可以证明 贪心算法greedySelector总能求得的整体最优解 即它最终所确定的相容活动集合A的规模最大 例1 活动安排问题 练习 已知待安排的11个活动的开始时间和结束时间 并且已经按结束时间的非减序排列如下 例1 活动安排问题 习题4 1 活动安排问题的贪心选择方案具有最短时段的相容活动覆盖未选择活动最少的相容活动 算法实现题4 1 会场安排问题算法1 用算法GreedySelector来安排会场算法2 对n个活动看做是实直线上的n个半闭活动区间 问题的实质是讨论n个活动区的最大重叠数m 若求得了最大重叠数m 则这m个重叠区所对应的活动互不相容 因此至少要安排m个会场来容纳这n个活动 1 将活动的开始和结束时间进行排序 2 扫描整个实直线 遇到一个si 则安排一个空闲会场 遇到一个fi 就释放一个会场为空闲备用 例2 最优装载 问题描述有一批集装箱要装上一艘载重量为c的轮船 其中集装箱i的重量为wi 1 i n 最优装载问题要求确定在装载体积不受限制的情况下 将尽可能多的集装箱装上轮船 例2 最优装载 分析 这个问题可以作为最优化问题进行描述 例2 最优装载 解决方案 船可以分步装载 每步装一个货箱 且需要考虑装载哪一个货箱 贪心准则 从剩下的货箱中 选择重量最小的货箱 这种选择次序可以保证所选的货箱总重量最小 从而可以装载更多的货箱 例2 最优装载 例如 n 8w 100 200 50 90 150 50 20 80 c 400 按照重量贪心原则 确定装载方案 解 所考察货箱的次序 7 3 6 8 4 1 5 2 最优解x 1 0 1 1 0 1 1 1 例2 最优装载 算法描述 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 例2 最优装载 分析 最优装载问题满足贪心选择性质和最优子结构性质 故算法正确 能求得最优解 时间复杂性 算法loading的主要计算量在于将集装箱依其重量从小到大排序 故算法所需的计算时间为O nlogn 例3 0 1背包问题 问题描述 给定n个物品和一个背包 物品i的重量为wi 其价值为vi 背包的容量为c 问 如何装物品 使得装入背包中物品总价值最大 例3 0 1背包问题 分析解决方案 分步装入 在每一步过程中利用贪心准则选择一个物品装入背包 至少有三种看似合理的贪心策略 重量贪心准则价值贪心准则价值密度贪心准则 例3 0 1背包问题 三种策略都不能保证得到最优解 例3 0 1背包问题 分析 三种贪心策略都不能保证得到最优解的原因重量贪心准则价值贪心准则价值密度贪心准则对于0 1背包问题 贪心选择不能得到最优解的原因是它无法保证最终能将背包装满 部分闲置背包空间使单位重量背包空间所具有的价值降低了 例3 0 1背包问题 事实上 在考虑0 1背包问题的物品选择时 应比较选择该物品和不选择该物品所导致的最终结果 然后再作出最好选择 由此导出许多互相重叠的子问题 这正是动态规划法求解问题的一个重要特征 动态规划法可以有效地解决0 1背包问题 例4 背包问题 问题描述 给定n个物品和一个背包 物品i的重量为wi 其价值为vi 背包的容量为c 问 如何装物品 使得装入背包中物品总价值最大 例4 背包问题 分析 贪心准则重量价值价值密度可以证明 按价值密度 单位价值 作为度量标准 背包问题达到最优解 例4 背包问题 例如 例4 背包问题 算法描述voidKnapsack intn floatM float v float w float x Sort n v w 按单位价值排序 for i 1 ic break x i 1 放入物品ic w i if i n x i c w i 例4 背包问题 算法分析 排序为算法的主要时间 故 T n O nlogn 贪心法与动态规划法的异同点 相同点要求问题具备最优子结构性质 不同点动态规划算法的另一个基本要素是重叠子问题性质 通常以自底向上的方式解各子问题 贪心算法通常以自顶向下的方式进行 以迭代的方式作出相继的贪心选择 每作一次贪心选择就将所求问题简化为规模更小的子问题 贪心选择性质 例5 多机调度问题 问题描述 多机调度问题要求给出一种作业调度方案 使所给的n个作业在尽可能短的时间内由m台机器加工处理完成 约定 每个作业均可在任何一台机器上加工处理 但未完工前不允许中断处理 作业不能拆分成更小的子作业 例5 多机调度问题 解决方案贪心算法短时优先需要短处理时间作业优先处理长时优先需要长处理时间作业优先处理注 长时优先 的贪心选择策略可以设计出解多机调度问题的较好的近似算法 例5 多机调度问题 长时优先 贪心算法的求解分析 当nm时 首先将n个作业依其所需的处理时间从大到小排序 然后依此顺序将作业分配给空闲的处理机 算法需要O nlogn 的计算时间 例5 多机调度问题 例如 设7个独立作业 1 2 3 4 5 6 7 所需的处理时间分别为 2 14 4 16 6 5 3 由3台机器M1 M3加工处理 J4 J2 J7 J5 J6 J3 J1 应用专题二 图问题中的贪心法例1 Huffman编码问题例2 单源点最短路径问题 Dijkstra算法例3 最小生成树问题 Prim算法例4 TSP问题 例1 Huffman编码 问题提出 通讯过程中需将传输的信息转换为二进制码 由于英文字母使用频率不同 若频率高的字母对应短的编码 频率低的字母对应长的编码 传输的数据总量就会降低 要求找到一个编码方案 使传输的数据量最少 分析 为能正确译码 编码需采用前缀码 前缀码和二叉树一一对应 问题可化为求一棵最优二叉树 例1 Huffman编码 贪心选择性设T为带权w1 w2 wt的最优树 带权w1和w2的树叶vw1和vw2是兄弟 以vw1和vw2为儿子的分枝点 其通路长度最长 最优子结构 设T为带权w1 w2 wt的最优树 若将以带权w1和w2的树叶为儿子的分枝点改为带权w1 w2的树叶 得到一棵新树T 则T 也是最优树 例1 Huffman编码 Huffman算法例如 求带权为2 2 3 3 5的最优二元树 例2 单源点最短路径 问题描述设给定一个带权有向图G V E 指定G中一个顶点vs为源点 现在要求出从vs到图中其余各个顶点之间的最短路径 该问题称为单源点最短路径问题 Dijkstra算法从图中的给定源点vs到其他各个顶点之间客观上应存在一条最短路径 在这组最短路径中 按路径长度递增次序 依次求出到不同顶点的最短路径长度 例2 单源点最短路径 基本思想 设置一个顶点集合S并不断作贪心选择来扩充该集合 Step1 初始时S vs 设置距离数组dist设u是G的某一顶点 dist u 记录vs到u且中间只经过S中顶点的路径的长度 Step2 从V S中取出最短路径长度的顶点u 将u添加到S中 同时对数组dist做必要的修正 Step3 算法重复Step2 直到S V dist就记录了从vs到所有其他顶点之间的最短路径长度 例2 单源点最短路径 例 单源点最短路径算法运行实例 v2 v4 v3 v5 v1 例3 最小生成树 基本定义子图生成子图生成树 例3 最小生成树 基本定义子图生成子图生成树一个连通无向图G V E 边权为W W1 W2 Wn 1 且T是G的生成树 其边权总和记为 W T 最小生成树T 例3 最小生成树 最小生成树的性质设一个连通带权图G V E S是V的一个真子集 如果边 u v E且u S v V S 而且所有这样的边 u v 的权cuv最小 则一定存在G的一棵最小生成树 它以 u v 为其中的一条边 证明 例3 最小生成树 分析 获得最小生成树的贪心方法是按照边的成本的和有最小增量为度量标准 逐条边地构造这棵树 根据使用贪心策略的不同 可以分为 Prim算法Kruskal算法 例3 最小生成树 Prim算法基本思想 先置S 1 只要S是V的真子集 就作如下的贪心选择 选取满足条件i S j V S且权c i j 最小的边 并将顶点j添加到S中 直到S V为止 注意 T始终是一棵树 例3 最小生成树 算法描述voidPrim T T存放最小生成树的边S 1 S存放最小生成树的顶点while S V i j i S j V S的最小权边 T T i j S S j 例3 最小生成树 Prim算法过程示例 v1 例3 最小生成树 Kruskal算法T V u0 v0 min cost u v u v分属不同的连通分量 将边 u0 v0 并入T的边集合TE 重复第2步 直至所有顶点在同一个连通分量中为止 注意 生成最小生成树的过程中 T一般是森林 最后才变为一棵树 例3 最小生成树 算法描述voidKruskal T T存放最小生成树的边while T的边少于n 1 从边集E中选一条最小权边 v w 从边集E中删去边 v w if 边 v w 在T中不生成环 将 v w 加到T else舍弃 v w 例3 最小生成树 Kruskal过程示例 例4 TSP问题 问题描述 例4 TSP问题 分析 求解TSP问题至少有两种贪心策略是合理的贪心策略贪心策略1 最近邻点策略贪心策略2 最短链接策略 贪心策略1 最近邻点策略 最近邻点策略 从任意城市出发 每次在没有到过的城市中选择最近的一个 直到经过了所有的城市 最后回到出发城市 例如 贪心策略1 最近邻点策略 贪心策略1 最近邻点策略 算法 输入 城市的数目n 代价矩阵c 起点城市v0输出 最小代价路线tour cost为最小代价tour 0 cost 0 v v0 V V v0 for k 1 k n k 查找与顶点v邻接的最小代价边 v w 并且w V tour v w cost c v w v w V V w tour v v0 cost c v v0 printf tour cost 贪心策略1 最近邻点策略 分析算法的时间复杂度O n2 注意 用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解 上图从城市1出发的最优解是1 2 5 4 3 1 总代价只有13 当图中顶点个数较多并且各边的代价值分布比较均匀时 最近邻点策略可以给出较好的近似解 不过 这个近似解以何种程度近似于最优解 却难以保证 贪心策略2 最短链接策略 最短链接策略每次在整个图的范围内选择最短边加入到解集合中 但是 要保证加入解集合中的边最终形成一个哈密顿回路 因此 当从剩余边集E 按照权值中选择一条边 u v 加入解集合S中 并尽可能权值小的边 应满足以下条件 边 u v 加入解集合S后 S中不产生回路 边 u v 加入解集合S后 S中不产生分枝 使权值尽可能小 贪心策略2 最短链接策略 例如 贪心策略2 最短链接策略 贪心策略2 最短链接策略 算法描述 顶点数 n 代价矩阵 c E 候选边集合 P 经过的边集 贪心策略2 最短链接策略 算法的时间性能分析 对于 两个顶点是否连通以及是否会产生分枝 的操作可以用并查集的操作将其时间性能提高到O n 如果操作 在E 中选取最短边 u v 用顺序查找 则选取最短边的操作可以是O n 此时算法的时间性能为O n2 如果采用堆排序的方法将集合E 中的边建立堆 则选取最短边的操作可以是O log2n 此时算法的时间性能为O nlog2n 应用专题三 贪心策略 不仅仅可以应用于最优化问题中 有时在解决构造类等问题时 用这种策略可以尽快地构造出一组解 其他应用专题例1 汽车加油问题例2 旅行家的预算例3 数列极差问题例4 删数问题例5 真分数分解问题例6 币种统计问题 例1 汽车加油问题 问题描述一辆汽车加满油后可以行驶nkm 旅途中有若干加油站 设计一个有效算法指出应在哪些加油站停靠加油 使沿途加油次数最少 分析贪心原则例如输入 输出77412345166 例2 旅行家的预算 问题描述 一个旅行家想驾驶汽车以最少的费用从一个城市到达第二个城市 假设出发前油箱是空的 给定两个城市之间的距离d 汽车油箱的容量c 每升汽油能行驶的距离m 出发点每升汽油的价格p0和沿途的加油站数目k 油站i离出发点的距离为di每升汽油的价格pi i 1 2 k 要求输出最小费用及加油方案 例2 旅行家的预算 分析 已知p i 表示第i站的油价d i 表示第i站距离出发点的距离设over i 表示第i站的余油量x i 表示第i站的加油量则 最省的加油方案是一组 x0 x1 x2 xk 1 使满足 例2 旅行家的预算 考虑如下问题出发前汽车的油箱是空的 那么汽车在起点处加油的量为多少 行程到第几站开始加油 加多少油 一般地 对于加油站i 下一个加油站j的油价低于加油站i 油箱需要 dj di m升汽油 若不能到达这样的油站 则至少需要到达下一个油站i 1后 继续进行考虑 此时应加满油箱 例2 旅行家的预算 算法描述 i 0 over x 0 L c m do 若 d i 1 d i L 输出无解 返回 在L内查找第1个低于i站油价的油站j if j存在 if over i 能到达j 计算到达j的余油over j else在i站购买油x i 使其刚好到达j站else在i站加满油 到达i 1站 并计算i 1站的余油 while未到达终点 例3 数列极差问题 问题描述 在黑板上写了N个正整数作成的一个数列 进行如下操作 每一次擦去其中的两个数a和b 然后在数列中加入一个数a b 1 如此下去直至黑板上剩下一个数 在所有按这种操作方式最后得到的数中 最大的记作max 最小的记作min 则该数列的极差定义为M max min 例3 数列极差问题 问题分析我们通过实例来认识题目中描述的计算过程 对三个具体的数据3 5 7讨论 可能有以下三种结果 3 5 1 7 1 113 3 7 1 5 1 111 5 7 1 3 1 109由此可见 先运算小数据得到的是最大值 先运算大数据得到的是最小值 例3 数列极差问题 一般地 任意三个数a b c 不妨假设a b c 则有以下几种组合计算结果 a b 1 c 1 a b c c 1 a c 1 b 1 a b c b 1 b c 1 a 1 a b c a 1显然此问题适合用贪婪策略不过在求最大值时 要先选择较小的数操作 反过来求最小值时 要先选择较大的数操作 这是一道两次运用贪心策略解决的问题 例3 数列极差问题 算法设计问题的解决方法和huffman树的构造过程相似 选取最大和最小的两个数二分法简单的逐个比较的方法来求解 注意 求max min的过程必须独立算法分析时间复杂度T n O n 空间复杂度S n O n 例4 删数问题 问题描述 n位整数a 去掉其中任意k个数字后 剩下的数字按原次序组成一个新的正整数 设计一种最小删数方案 使得剩下得数字组成的新数最小 问题分析贪心法求解 删k个数符的全局最优解 包含了删除1个数符的子问题的最优解 以字串形式输入a 使用尽可能逼近目标的贪心法来逐一删去其中的k个数符 每一步总是选择一个能使剩下的数最小的数符删去 例4 删数问题 例如 a 178543 k 4a 278594513 k 6贪心准则 最近下降点优先按照高位 低位搜索递减区间 若存在递减区间 则删去该区间的首字符 否则删去尾字符 重复上述规则 删下一个字符 依此类推 直至删去k个字符为止 例5 真分数分解 问题描述 设计一个算法 把一个真分数表示为埃及分数之和的形式 所谓埃及分数 是指分子为1的形式 如 7 8 1 2 1 3 1 24 问题分析基本思想 逐步选择分数所包含的最大埃及分数 这些埃及分数之和就是问题的一个解 如 7 8 1 27 8 1 2 1 37 8 1 2 1 3 1 24 故 7 8 1 2 1 3 1 24 例5 真分数分解 问题的求解过程 1 找最小的n 也就是最大的埃及分数 使分数f