算法设计与分析 ——贪心法
贪心算法 主要内容: 介绍贪心法的基本原理,贪心算法设计的基本方法和应用例子 。
贪心算法 一.贪心法的基本原理 1. 一个例子 贪心法是一种算法设计技术,通常用于求解最优化问题。 例1. 找钱问题:设有4种硬币,面值分别为25分,10分,5分和1分,要找出63分钱,问如何找钱可使得找出的硬币个数最少? 是否所有找钱问题都可用贪心法解?
贪心算法 一. 贪心法的基本原理 2. 贪心法的基本思想 基本思想: 通过一系列选择步骤来构造问题的解,每一步都是对当前部分解的一个扩展,直至获得问题的完整解。所做的每一步选择都必须满足: 1)可行的:必须满足问题的约束。 2)局部最优:当前所有可能的选择中最佳的局部选择。 3)不可取消: 选择一旦做出,在后面的步骤中就无法改变了。
贪心算法 一. 贪心法的基本原理 2. 贪心法的基本思想 贪心算法的几个经典例子: Dijkstra算法:求有向图的单源最短路径(8.2) Kruskal算法:求最小生成树 (8.3) Prim算法:求最小生成树 (8.4) Huffman树、Huffman编码的算法 (8.5)
贪心算法 一. 贪心法的基本原理 按贪心法解得: 25分 1个, 1分5个, 共6个 2. 贪心法的基本思想 贪心法不能保证总能得到最优解(一系列的局部最优选择不能保证最后得到整体最优解) 例2. 另一个找钱问题:设有3种硬币,面值分别为25分,10分和1分,要找出30分钱,问如何找钱可使得找出的硬币个数最少? 按贪心法解得: 25分 1个, 1分5个, 共6个 问题的最优解:10分3个
贪心算法 一. 贪心法的基本原理 两活动ai , aj (i≠j)相容是指: 2. 贪心法的基本思想 贪心算法的关键:贪心选择策略的确定。 例3. 活动安排问题:设有n个活动a1, a2, …, an , 每个活动都要求使用同一资源,而同一时间内只允许一个活动使用这一资源。已知活动ai要求使用该资源的起始时间为si,结束时间为fi,且si<= fi 。要求在a1, a2, …, an中选出最大的相容活动子集。 两活动ai , aj (i≠j)相容是指:
贪心算法 一. 贪心法的基本原理 si: 4 2 1 8 fi : 7 4 5 10 2. 贪心法的基本思想 例:n=4 , 活动: a1 a2 a3 a4 si: 4 2 1 8 fi : 7 4 5 10 贪心选择策略:按结束时间从早到晚安排活动,每次选择与已选出的活动相容的结束时间尽可能早的活动。 局部最优性:每次为资源留下尽可能多的时间以容纳其它活动。
贪心算法 贪心算法 结果:最大相容子集A={1,4,8,11} i si fi 1 4 2 3 5 6 7 8 9 10 11 12 13 6 7 8 9 10 11 12 13 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 贪心算法 结果:最大相容子集A={1,4,8,11}
贪心算法 一. 贪心法的基本原理 2. 贪心法的基本思想 贪心算法的特点:贪心算法往往效率高,一般时间复杂性为多项式阶。贪心算法一般较简单,其关键和难点在于贪心选择策略的确定,以及证明相应的贪心算法确实可求出最优解。
贪心算法 一.贪心法的基本原理 2.贪心法的基本思想 活动安排问题的贪心选择策略的正确性证明:证明贪心算法ACTIVITY_ARRANGEMENT求出的解为最优解。 证明思路:任意一个最优解都可通过替换变成该贪心算法求出的解,而且解的最优性不变。 贪心法除了用于求一些问题的最优解外,常用于求问题的近似最优解。
贪心算法 一. 贪心法的基本原理 2. 贪心法和动态规划 贪心法:每一步的选择不依赖于其子问题的解,选择是局部最优的,但不能保证最终得到最优解。 动态规划:问题的解依赖于其子问题的解,选择是全局最优的,可保证最终得到最优解。
贪心算法 二. 贪心算法设计示例 1. 分数背包问题 问题描述:设有一个容量为C的背包,n个物品的集合U={u1, u2, …, un},物品ui的体积和价值分别为sj和vj,C, sj, vj都是正实数。在U中选择物品装入背包,使得装入背包的物品总价值最大。设允许取每种物品的一部分装入背包。
贪心算法 二. 贪心算法设计示例 1. 分数背包问题 数学模型: z=max v1x1+ v2x2+…+ vnxn s1x1+ s2x2+…+ snxn<=C 0<= xi <=1, i=1, 2, …, n 解的意义: xi表示物品i装入背包的部分占该物品全部的比例。
贪心算法 二. 贪心算法设计示例 1. 分数背包问题 例:n=3, C=20 物品: u1 u2 u3 体积si: 18 15 10 价值vi: 25 24 15 贪心选择策略:按单位体积价值从大到小的顺序选择物品装入背包。 贪心算法
贪心算法 二. 贪心算法设计示例 2.有期限的作业安排问题 问题描述: 给定n个作业j1, j2, …, jn,作业ji 的期限为di 收益为pi , di , pi为非负整数, i=1, 2, …, n。规定只有在期限di内完成任务ji才能得到收益pi。设只有一台处理机,同时只能处理一个作业,且完成每个作业都需要一个单位时间。问如何安排作业处理顺序使得总收益最大? 该问题就是求一个作业序列 使得 。
贪心算法 二. 贪心算法设计示例 2.有期限的作业安排问题 例:n=4 , 作业: j1 j2 j3 j4 期限di: 2 3 1 3 收益pi: 100 150 200 250 贪心选择策略:按收益从高到低的顺序逐个安排作业的处理顺序,在不影响收益高的作业的期限的前提下,尽量让期限早的作业先处理。
贪心算法 二. 贪心算法设计示例 2.有期限的作业安排问题 贪心算法:贪心算法 要点: 1)先将 n个作业按收益从高到低排序,按排序的结果顺序 考虑作业安排。 2)已安排的作业序列始终按期限从早到晚的顺序排列。 3)当安排某作业会使得已安排的作业超期时,舍弃当前作业。
贪心算法 二. 贪心算法设计示例 3. 最小生成树(Prim算法) 有关概念: 生成树:设G=(V, E)为连通图,G的生成树是G的包含其所有顶点的极小连通子图(这里极小的含义是包含的边最少)。 一个连通图的生成树不一定唯一。 含n个顶点的连通图的生成树恰含n-1条边。 最小生成树:设G=(V, E)为连通网,G的最小代价的生成树称为G的最小生成树。
贪心算法 二. 贪心算法设计示例 3. 最小生成树(Prim算法) 有关概念: 生成树的代价:生成树边上的权值总和。 最小生成树是否唯一? 求最小生成树就是求出其n-1条边。
贪心算法 二. 贪心算法设计示例 T= ; X={1}; Y=V-{1}; 3. 最小生成树(Prim算法) Prim算法的基本思想 设连通图G=(V, E), V={1, 2, …, n}, G的最小生成树的边集为T, 从一个顶点开始生成G的最小生成树: T= ; X={1}; Y=V-{1}; while Y 从{(u, v)| u X, v Y}中选出最小权值的边(x, y); X=X {y}; Y=Y-{y}; T=T {(x, y)} end while (图例: 图8.5 (P154) )
贪心算法 二. 贪心算法设计示例 Prim算法: Prim算法 算法的正确性 MST性质:设G=(V, E)是一个连通网,U为V的一个非空真子集。若(u, v)是满足u U, v V-U的具有最小权值的边,则必存在一棵包含边(u, v)的最小生成树。