算法设计与分析 ——贪心法. 算法设计与分析 ——贪心法 贪心算法 主要内容： 介绍贪心法的基本原理，贪心算法设计的基本方法和应用例子 。

Presentation on theme: "算法设计与分析 ——贪心法. 算法设计与分析 ——贪心法 贪心算法 主要内容： 介绍贪心法的基本原理，贪心算法设计的基本方法和应用例子 。"— Presentation transcript:

1

2 算法设计与分析 ——贪心法

3 贪心算法 主要内容： 介绍贪心法的基本原理，贪心算法设计的基本方法和应用例子 。

4 贪心算法 一.贪心法的基本原理 1. 一个例子 贪心法是一种算法设计技术，通常用于求解最优化问题。
例1. 找钱问题：设有4种硬币，面值分别为25分，10分，5分和1分，要找出63分钱，问如何找钱可使得找出的硬币个数最少？ 是否所有找钱问题都可用贪心法解？

5 贪心算法 一. 贪心法的基本原理 2. 贪心法的基本思想 基本思想：
通过一系列选择步骤来构造问题的解，每一步都是对当前部分解的一个扩展，直至获得问题的完整解。所做的每一步选择都必须满足： 1）可行的：必须满足问题的约束。 2）局部最优：当前所有可能的选择中最佳的局部选择。 3）不可取消: 选择一旦做出，在后面的步骤中就无法改变了。

6 贪心算法 一. 贪心法的基本原理 2. 贪心法的基本思想 贪心算法的几个经典例子： Dijkstra算法：求有向图的单源最短路径（8.2）
Kruskal算法：求最小生成树 (8.3) Prim算法：求最小生成树 (8.4) Huffman树、Huffman编码的算法 (8.5)

7 贪心算法 一. 贪心法的基本原理 按贪心法解得: 25分 1个， 1分5个， 共6个 2. 贪心法的基本思想
贪心法不能保证总能得到最优解（一系列的局部最优选择不能保证最后得到整体最优解） 例2. 另一个找钱问题：设有3种硬币，面值分别为25分，10分和1分，要找出30分钱，问如何找钱可使得找出的硬币个数最少？ 按贪心法解得: 25分 1个， 1分5个， 共6个 问题的最优解：10分3个

8 贪心算法 一. 贪心法的基本原理 两活动ai , aj (i≠j)相容是指： 2. 贪心法的基本思想 贪心算法的关键：贪心选择策略的确定。
例3. 活动安排问题：设有n个活动a1, a2, …, an , 每个活动都要求使用同一资源，而同一时间内只允许一个活动使用这一资源。已知活动ai要求使用该资源的起始时间为si，结束时间为fi，且si<= fi 。要求在a1, a2, …, an中选出最大的相容活动子集。 两活动ai , aj (i≠j)相容是指：

9 贪心算法 一. 贪心法的基本原理 si： 4 2 1 8 fi ： 7 4 5 10 2. 贪心法的基本思想
例：n=4 , 活动： a1 a2 a3 a4 si： fi ： 贪心选择策略：按结束时间从早到晚安排活动，每次选择与已选出的活动相容的结束时间尽可能早的活动。 局部最优性：每次为资源留下尽可能多的时间以容纳其它活动。

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}

11 贪心算法 一. 贪心法的基本原理 2. 贪心法的基本思想
贪心算法的特点：贪心算法往往效率高，一般时间复杂性为多项式阶。贪心算法一般较简单，其关键和难点在于贪心选择策略的确定，以及证明相应的贪心算法确实可求出最优解。

12 贪心算法 一.贪心法的基本原理 2．贪心法的基本思想 活动安排问题的贪心选择策略的正确性证明：证明贪心算法ACTIVITY_ARRANGEMENT求出的解为最优解。 证明思路：任意一个最优解都可通过替换变成该贪心算法求出的解，而且解的最优性不变。 贪心法除了用于求一些问题的最优解外，常用于求问题的近似最优解。

13 贪心算法 一. 贪心法的基本原理 2. 贪心法和动态规划
贪心法：每一步的选择不依赖于其子问题的解，选择是局部最优的，但不能保证最终得到最优解。 动态规划：问题的解依赖于其子问题的解，选择是全局最优的，可保证最终得到最优解。

14 贪心算法 二. 贪心算法设计示例 1. 分数背包问题 问题描述：设有一个容量为C的背包，n个物品的集合U={u1, u2, …, un}，物品ui的体积和价值分别为sj和vj，C, sj, vj都是正实数。在U中选择物品装入背包，使得装入背包的物品总价值最大。设允许取每种物品的一部分装入背包。

15 贪心算法 二. 贪心算法设计示例 1. 分数背包问题 数学模型： z=max v1x1+ v2x2+…+ vnxn
s1x1+ s2x2+…+ snxn<=C 0<= xi <=1, i=1, 2, …, n 解的意义: xi表示物品i装入背包的部分占该物品全部的比例。

16 贪心算法 二. 贪心算法设计示例 1. 分数背包问题 例：n=3, C=20 物品： u1 u2 u3 体积si： 18 15 10
价值vi： 贪心选择策略：按单位体积价值从大到小的顺序选择物品装入背包。 贪心算法

17 贪心算法 二. 贪心算法设计示例 2.有期限的作业安排问题
问题描述: 给定n个作业j1, j2, …, jn，作业ji 的期限为di 收益为pi , di , pi为非负整数, i=1, 2, …, n。规定只有在期限di内完成任务ji才能得到收益pi。设只有一台处理机，同时只能处理一个作业，且完成每个作业都需要一个单位时间。问如何安排作业处理顺序使得总收益最大？ 该问题就是求一个作业序列 使得 。

18 贪心算法 二. 贪心算法设计示例 2.有期限的作业安排问题 例：n=4 , 作业： j1 j2 j3 j4 期限di： 2 3 1 3
收益pi： 贪心选择策略：按收益从高到低的顺序逐个安排作业的处理顺序，在不影响收益高的作业的期限的前提下，尽量让期限早的作业先处理。

19 贪心算法 二. 贪心算法设计示例 2.有期限的作业安排问题 贪心算法：贪心算法 要点：
1）先将 n个作业按收益从高到低排序，按排序的结果顺序 考虑作业安排。 2）已安排的作业序列始终按期限从早到晚的顺序排列。 3）当安排某作业会使得已安排的作业超期时，舍弃当前作业。

20 贪心算法 二. 贪心算法设计示例 3. 最小生成树（Prim算法） 有关概念：
生成树：设G=(V, E)为连通图，G的生成树是G的包含其所有顶点的极小连通子图(这里极小的含义是包含的边最少)。 一个连通图的生成树不一定唯一。 含n个顶点的连通图的生成树恰含n-1条边。 最小生成树：设G=(V, E)为连通网，G的最小代价的生成树称为G的最小生成树。

21 贪心算法 二. 贪心算法设计示例 3. 最小生成树（Prim算法） 有关概念： 生成树的代价：生成树边上的权值总和。 最小生成树是否唯一？
求最小生成树就是求出其n-1条边。

22 贪心算法 二. 贪心算法设计示例 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) ）

23 贪心算法 二. 贪心算法设计示例 Prim算法： Prim算法 算法的正确性
MST性质：设G=(V, E)是一个连通网，U为V的一个非空真子集。若(u, v)是满足u U, v V-U的具有最小权值的边，则必存在一棵包含边(u, v)的最小生成树。