20151112-JWJ-Algorithm-12-贪心算法
湖南大学-算法设计与分析课程
Lecture 12-贪心算法
办公室：信息科学与工程学院院楼326 2015-2016第一学期
回 顾
动态规划6案例， 矩阵连乘、最长公共子序列、 最大子段和可扩展、 凸多边形最优三角剖分、 多边形游戏更一般、 0-1背包为经典。 动态规划四步骤， 按部就班得最优。
2015-11-12
算法设计与分析B【CS06081】
2
棋盘覆盖、 二分搜索技术、 归并排序、 大整数乘法 快速排序、 线性时间选择
最接近点对、 循环赛日程表
主要内容
回 溯 法 分 支 限 界 法
最大子段和、 最长公共子序列 加括号矩阵连乘
凸多边形最优三角剖分 多边形游戏
递 归 与 分 治
动 态 规 划
贪 心 算 法
随 机 化 算 法
线 性 规 划 算 法
并行文件系统 ACM竞赛培训 屠呦呦-医学诺贝尔奖 酷炫页面制作 ACM中国暨物联网设计大赛
互联网的发展阶段 小世界网络 pagerank算法 推荐系统与算法
IT就业经验谈
2015-11-12
算法设计与分析B【CS06081】
3
贪心算法
• 贪心算法的基本思想 • 贪心算法的基本要素
– 最优子结构性质 – 贪心选择性质
• 贪心算法与动态规划算法的差异 • 案例
– （1）背包问题 – （2） 活动安排问题 – （3）最优装载问题
2015-11-12
算法设计与分析B【CS06081】
4
贪心算法的基本思想
将问题的求解过程看作是一系列选择,每次选择 一个输入,每次选择都是当前状态下的最好选择( 局部最优解).每作一次选择后,所求问题会简化 为一个规模更小的子问题.从而通过每一步的最 优解逐步达到整体的最优解。
2015-11-12
算法设计与分析B【CS06081】
5
贪心算法的基本思想
[适用问题] 具备贪心选择和最优子结构性质的最优化问题
整体的最优解可通过一系列 局部最优解达到； 每次选择依赖于当前， 不依赖于之后 整体的最优解包含 子问题的最优解
[常见应用] 背包问题,最小生成树,最短路径,作业调度等等 [算法优点] 求解速度快,时间复杂性有较低的阶. [算法缺点] 需证明是最优解.
2015-11-12 算法设计与分析B【CS06081】 6
贪心算法的基本要素 -贪心选择性质
• 概念
– 所求问题的整体最优解可以通过一系列局部最优的 选择，即贪心选择来达到。
• 做法
– 要确定一个具体问题是否具有贪心选择性质，必须 证明每一步所作的贪心选择最终导致问题的整体最 优解。
2015-11-12
算法设计与分析B【CS06081】
7
贪心算法的基本要素 -最优子结构性质
• 概念
– 当一个问题的最优解包含其子问题的最优解时，此 问题具有最优子结构性质。 – 问题的最优子结构性质是该问题可用动态规划算法 或贪心算法求解的关键特征。
2015-11-12
算法设计
与分析B【CS06081】
8
贪心算法的基本解题思路
• 建立数学模型来描述问题。 • 把求解的问题分成若干个子问题。 • 对每一子问题求解，得到子问题的局部最优解。 • 把子问题的解局部最优解合成原来解问题的一个解。
2015-11-12
算法设计与分析B【CS06081】
9
贪心算法与动态规划算法的异同
共同点:都要求问题具有最优子结构性质。 不同点：动态规划算法通常以自底向上的方式解各子 问题，而贪心算法则通常以自顶向下的方式进行，以 迭代的方式作出相继的贪心选择，每作一次贪心选择 就将所求问题简化为规模更小的子问题。
2015-11-12
算法设计与分析B【CS06081】
10
案例分析1
- 背包问题和0-1背包问题
0-1背包问题描述：
给定n种物品和一背包。 物品i的重量是wi，其价 值为vi，背包的容量为C 。问应如何选择装入背 包的物品，使得装入背 包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有2种选择 ，即装入背包或不装入背包。不能将物品i装入背包 多次，也不能只装入部分的物品i。
2015-11-12 算法设计与分析B【CS06081】 11
案例分析1
- 背包问题和0-1背包问题
背包问题 (Knapsack Problem) [问题描述]设有n个物体和一个背包,物体i的重量为wi ,价值为 vi ,背包的容量为C.若将物体i的xi部分(1in, 0xi1)装入 背包,则具有价值为vi xi. 目标是找到一个方案,使放入背包的 物体总价值最高. n wi xi c [最优化描述] 找一个n元向量(x1,…xn) 0 xi 1 使得 i 1 且 max
v x .其中
i 1 i i
n
C, Wi, vi>0 , 1 i n 约 束 条 件
优化函数
算法设计与分析B【CS06081】
2015-11-12
12
案例分析1
- 背包问题和0-1背包问题 • 背包问题
VS
0-1背包问题
这2类问题都具有最优子结构性质，极为相似，但背包 问题可以用贪心算法求解，而0-1背包问题却不能用贪 心算法求解。
2015-11-12
算法设计与分析B【CS06081】
13
背包问题实例
• 考虑下列情况的背包问题 – n=3, c=20, (v1,v2,v3)=(25,24,15), (w1,w2,w3)=(18,15,10) – 其中的4个可行解是：
(x1,x2,x3) ① ② ③ ④
2015-11-12
∑wi xi 16.5 20 20 20
∑vixi 24.25 28.2 31 31.5
14
(1/2,1/3,1/4) (1,2/15,0) (0,2/3,1) (0,1,1/2)
算法设计与分析B【CS06081】
贪心方法的数据选择策略(1)
1、用贪心策略求解背包问题时，首先要选出最优的度 量标准。可以选取目标函数为量度标准，每装入一件物品就 使背包获得最大可能的效益值增量。在这种量度标准下的贪 心方法就是按效益值的非增次序将物品一件件放到背包中。 如上面的实例所示，可将物品按效益量非增次序排序： (v1,v2,v3)=(25,24,15)。先装入物品1重量为18，即x1=1；然后再 装物品2，由于约束条为
∑wi xi ≤c=20，所以物品2只能装入重 量为2的一小部分，即x2=2/15。 按上述的数据选择策略，装入顺序是按照物品的效益值从 大到小的输入，由刚才的方法可得这种情况下的总效益值为 ∑ vixi = 25+24*2/15=28.2 ，显然是一个次优解，原因是背包容 量消耗过快。
2015-11-12 算法设计与分析B【CS06081】 15
贪心方法的数据选择策略(2)
2 、若以容量作为量度，可让背包容量尽可能慢 地被消耗。这就要求按物品重量的非降次序来把物品 放入背包，即(w3,w2,w1)=(10,15,18)。 先装入物品3, x3=1, p3x3 =15，再装入重量为10的 物品2， ∑vixi =15+24*10/15=31。 由刚才的方法可得这种情况下的总效益值为31， 仍是一个次优解，原因是容量在漫漫消耗的过程中， 效益值却没有迅速的增加。
2015-11-12
算法设计与分析B【CS06081】
16
贪心方法的数据选择策略(3)
3 、采用在效益值的增长速率和容量的消耗速率之 间取得平衡的量度标准。即每一次装入的物品应使它占 用的每一单位容量获得当前最大的单位效益。这就需使 物品的装入次序按vi/wi比值的非增次序来考虑。 这种策略下的量度是已装入物品的累计效益值与所 用容量之比。 (v2/w2 , v3/w3 , v1/w1 )=(24/15,15/10, 25/18) 先装入重量为15的物品2，再装入重量为5的物品3, ∑pixi =24+15*5/10=31.5。此结果为最优解。
2015-11-12 算法设计与分析B【CS06081】 17
[例] n=3,c=20 (v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10) {x1,x2,x3}{1,2/15,0}{ 0,2/3,1}{0,1,1/2} {...}
i 1
n
wi xi
i i
n
20 28.2
20 31
20 31.5
vx
i 1
. ... . .
[算法思路]1).将各物体按单位价值由高到低排序. 2).取价值最高者放入背包. 3).计算背包剩余空间. 4).在剩余物体中取价值最高者放入背包. 若背包剩余容量=0或物体全部装入背包为止
2015-11-12 算法设计与分析B【CS06081】 18
案例分析1
- 背包问题和0-1背包问题
void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w); int i; for (i=1;ic) break; x[i]=1; c-=w[i]; } if (i
2015-11-12 算法设计与分析B【CS06081】 19
算法knapsack 的主要计算时间在 于将各种物品依其 单位重量的价值从 大到小排序。因此 ，算法的计算时间 上界为 O（nlogn）。 为了证明算法的正 确性，还必须证明 背包问题具有贪心 选择性质。
案例分析1
- 背包问题和0-1背包问题
对于0-1背包问题，贪心选择之所以不能得到最优 解是因为在这种情况下，它无法保证最终能将背 包装满，部分闲置的背包空间使每公斤背包空间 的价值降低了。 在考虑0-1背包问题时，应比较选择该物品和不选 择该物品所导致的最终方案，然后再作出最好选 择。由此就导出许多互相重叠的
子问题。这正是 该问题可用动态规划算法求解的另一重要特征。
2015-11-12
算法设计与分析B【CS06081】
20
案例分析2
- 活动安排问题 问题描述：
设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用 同一资源，如演讲会场等，而在同一时间内只有一个活动能 使用这一资源。每个活动i都有一个要求使用该资源的起始时 间si和一个结束时间fi,且si
2015-11-12 算法设计与分析B【CS06081】 21
案例分析2
- 活动安排问题
• 该问题要求高效地安排一系列争用某一公共 资源的活动。 • 贪心算法提供了一个简单、漂亮的方法使得 尽可能多的活动能兼容地使用公共资源。
2015-11-12
算法设计与分析B【CS06081】
22
案例分析2
- 活动安排问题
[算法思路]将n个活动按结束时间非减序排列,依次考虑活动i, 若i与已选择的活动相容,则添加此活动到相容活动子集. [例] 设待安排的11个活动起止时间按结束时间的非减序排列 i 1 2 3 4 5 6 7 8 9 10 11 s[i] 1 3 0 5 3 5 6 8 8 2 12 f[i] 4
5
6
7
8
9
10 11
12
13 14
最大相容活动子集(1, 4, 8, 11), 也可表示为等长n元数组:(1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1)
2015-11-12
算法设计与分析B【CS06081】
23
案例分析2
- 活动安排问题
算法greedySelector 的计算过程如左图所 示。图中每行相应于 算法的一次迭代。阴 影长条表示的活动是 已选入集合A的活动， 而空白长条表示的活 动是当前正在检查相 容性的活动。
2015-11-12
算法设计与分析B【CS06081】
24
案例分析2
- 活动安排问题
template void GreedySelector(int n, Type s[], Type f[], bool A[]) { A[1]=true; int j=1; for (int i=2;i=f[j]) { A[i]=true; j=i; } else A[i]=false; } }
2015-11-12 算法设计与分析B【CS06081】 25
各活动的起始时间和结 束时间存储于数组s和f 中且按结束时间的非减 序排列
案例分析2
- 活动安排问题
由于输入的活动以其完成时间的非减序排列，所以算法 greedySelector每次总是选择具有最早完成时间的相容 活动加入集合A中。直观上，按这种方法选择相容活动 为未安排活动留下尽可能多的时间。也就是说，该算法 的贪心选择的意义是使剩余的可安排时间段极大化，以 便安排尽可能多的相容活动。 算法greedySelector的效率极高。当输入的活动已按结束 时间的非减序排列，算法只需O(n)的时间安排n个活动， 使最多的活动能相容地使用公共资源。如果所给出的活
动 未按非减序排列，可以用O(nlogn)的时间重排。
2015-11-12 算法设计与分析B【CS06081】 26
案例分析2
- 活动安排问题
贪心算法并不总能求得问题的整体最优解。但对于 活动安排问题，贪心算法greedySelector却总能求得 的整体最优解，即它最终所确定的相容活动集合A的 规模最大。这个结论可以用数学归纳法证明。
2015-11-12
算法设计与分析B【CS06081】
27
案例分析3
- 最优装载
问题描述： 有一批集装箱要装上一艘载重量为c的轮船。其中集装 箱i的重量为Wi。最优装载问题要求确定在装载体积不 受限制的情况下，将尽可能多的集装箱装上轮船。
[数学模型] 输入:(x1,x2,...xn), xi=0,货箱i不装船; n xi=1,货箱i装船。 wi x i 可行解: 满足约束条件 ≤c 的输入 n i 1 优化函数: x i i 1 最优解:使优化函数达到最大值的一种输入.
2015-11-12 算法设计与分析B【CS06081】 28
案例分析3
- 最优装载
[算法思路] 将装船过程划为多步选择，每步装一个货 箱，每次从剩下的货箱中选择重量最轻的货箱.如此下 去直到所有货箱均装上船或船上不能再容纳其他任何一 个货箱。
[例] 设n=8，[w1，…w8]=[100, 200, 50, 90, 150, 50, 20, 80]，c=400。
所考察货箱的次序为 :7, 3, 6, 8, 4, 1, 5, 2。货箱7, 3, 0, 1, 6, 8, 4, 1的总重量为390个单位且已被装载, 剩下的装载能力为 10 ,小于任意货箱.所以得到解[x1,...x8]=[ 1, 0, 1, 1, 1, 1]
2015-11-12 算法设计与分析B【CS06081】 29
案例分析3
- 最优装载
template void Loading(int x[], Type w[], Type c, int n) { int *t = new int [n+1]; Sort(w, t, n); for (int i = 1; i
2015-11-12 算法设计与分析B【CS06081】 30
案例分析3
- 最优装载
贪心选择性质 最优子结构性质 最优装载问题具有最优子结构性质。 由最优装载问题的贪心选择性质和最优子结构性质， 容易证明算法loading的正确性。
算法loading的主要计算量在于将集装箱依其重量从小到大 排序，故算法所需的计算时间为 O(nlogn)。
2015-11-12 算法设计与分析B【CS06081】 31
总 结
贪心算法很直观， 专注眼前不后看。 贪心选择、最优子结构两要素， 背包问题可贪心， 0-1背包只动态。 活动安排、最优装载为两例，
2015-11-12
算法设计与分析B【CS06081】
32
谢 谢!
E-mail: [email protected]
2015-11-12
湖南大学 -算法设计与分析 算法设计与分析B【CS06081】
33