计算机算法设计与分析第4章(1)

• 然后，证明该问题具有最优子结构性质。在贪心 选择了e1后，原问题简化为对E中所有与e1相容的 活动进行活动安排的子问题。
– 即证明，若A是原问题的一个最优解，则A’ = A - {e1}是 活动安排问题E’ = ,i∈E: si ≥ f1}的一个最优解。 – 如若不然，假设我们找到E’的一个解B’，它包含比A’更 多的活动，则将e1加入到B’中将产生E的一个解B，它包 含比A更多的活动。这与A是原问题的最优解相矛盾。 – 因此，每一步所作的贪心选择都将问题简化为一个更 小的与原问题具有相同形式的子问题。
设待安排的11个活动的开 始时间和结束时间按结束 时间的非减序排列如下：
i 1 si 1 fi 4
2
3 4 5 6 7 8 9 10 11
3
0 5 3 5 6 8 8 2 12
5
6 7 8 9 10 11 12 13 14
• 算法分析
– 算法的效率很高。当输入的活动已按结束时间 非减序排列时，算法只需O(n)的时间安排n个活 动，使最多的活动能相容地使用公共资源。如 果所给出的活动未按非减序排列，可以用 O(nlogn)的时间预排序。
• 例如活动安排问题中，B = A - {ek}∪{ej}
最优装载
• 有一批集装箱要装上一艘载重为c的轮船。 其中集装箱i的重量为wi。最优装载问题要 求确定，在装载体积不受限制的情况下， 应如何装载才能将尽可能多的集装箱装上 轮船。 • 形式化描述为： xi {0,1}, 1 i n 解向量
已证原问题的一个最优解是以贪心选择开始。假设i次贪心选择能够得到一 个最优解，那么i+1次贪心选择也能得到一个最优解。
• 对贪心选择次数用数学归纳法即知，该贪 心算法最终产生原问题的一个最优解。
i次贪心选择 非贪心策略所选 按结束时间排序 的结果
考察原问题的一个最优解A = {e1, … , ei, ek, … （修改A）令B = {e1, … , ei, ej, …
– 设(x1,x2,…,xn)是最优装载问题的一个满足贪心选 择性质的最优解，则x1=1，(x2,…,xn)是轮船载重 为c-w1且待装船集装箱为,2,3,…,n-时相应最优装 载问题的一个最优解。
• 因此，最优装载问题具有贪心选择性质和 最优子结构性质，采用“重量最轻者先装” 的贪心选择策略能够得到整体最优解。
… , x i , x k, … （修改A）令B={x1, … , xi, xj, …
-
证明用xj替换xk后能够得到另 一个最优解B，B=A-{xk}∪{xj}
第i+1次贪心选择的结果
贪心算法的基本思路
• 根据题意，选取一种贪心选择策略，然后按这种策略对n 个输入排序，按顺序一次输入一个值。如果这个输入和当 前已构成的部分最优解加在一起不能产生一个可行解，则 不把此输入加到这部分解中。
用ej替换ek，因fj<fk，故得到 另一个最优解B=A-{ek}∪{ej}
-
E-{e1,…,ei}中具有最早结束 时间且与ei相容的活动
最早结束时间 原 问 题 的 n 个 活 动 排 序 后 的 n 个 活 动 与最近一次加入的 活动相容 A’(1) A’(j) S(1) S(2) …
A(1) A(2) … A(n)
第四章 贪心算法
(Greedy)
背包问题
• 给定n种物品和一个背包。物品i的重量是wi，其价 值为vi，背包的容量为c。问应如何选择装入背包 的物品，使得装入背包中物品的总价值最大? • 在选择物品i装入背包时，可以选择物品i的一部分， 而不一定要全部装入。
约束条件
目标函数 解向量
w x
i 1 n
3. 若将这种物品全部装入背包后，背包内物品的总重量 未超过背包的载重M，则选择单位重量价值次高的物品 并尽可能多地装入 Knapsack_greedy(n, M, v[], w[], x[]) O(nlogn) Sort(n,v,w) for i = 1 to n do // 初始化解向量 x[i] = 0 c=M // c是背包当前载重 O(n) for i = 1 to n do if w[i] > c break x[i] = 1 c = c - w[i] if i ≤ n x*i+ = c/w*i+ // 装入第i个物品的一部分
– 最优子结构性质是该问题可用动态规划算法或 贪心算法求解的关键特征。
活动安排问题
• 要求高效地安排一系列争用某一公共资源（例如 会议室）的活动（使尽可能多的活动能兼容使用 公共资源）。
– 设有n个活动的集合E={e1,e2…en}，其中每个活动都要求 使用同一资源，而在同一时间内只有一个活动能使用 这一资源。每个活动i都有一个要求使用该资源的起始 时间si和一个结束时间fi，且si<fi。如果选择了活动i，则 它在半开时间区间[si,fi)内占用资源。 – 若区间[si,fi)与区间[sj,fj)不相交，则称ei和ej是相容的。 也就是说，当si≥fj或sj≥fi时，活动i和活动j相容。
对于活动安排问题，每次选择具有最早结束时间的活动能够得 到整体最优解，即它最终所确定的相容活动集合A的规模最大。
设E={e1,e2…en}是按结束时间排序的活动集合， 则e1具有最早的结束时间。
• 首先，证明该问题具有贪心选择性质。也就是说， 该问题有一个最优解以贪心选择开始，即该最优 解中包含e1。
ith a1 , … , ai
, ai+1, … , an
ith
a1
…
ai
, ai+1, … , an
sorted
贪心算法 vs. 动态规划
• 在动态规划算法中，每步所做的选择往往依赖于 相关子问题的解，因而只有在解出相关子问题后， 才能做出选择。
根据子问题的解进行选择
• 而在贪心算法中，仅在当前状态下做出最好选择， 即局部最优选择，然后再去解做出这个选择后产 生的相应的子问题。
– 设A是所给活动安排问题的一个最优解。将A中活动也 按结束时间非减序排列，则A中的第一个活动是ek。 – 若k=1，则A就是一个以贪心选择开始的最优解。 – 若k>1，则我们设B = A - {ek}∪{e1}。//用e1替换ek – 由于f1≤fk，且A中活动是相容的，故B中的活动也是相容 的。又由于B中活动个数与A中活动个数相同，且A是最 优的，故B也是最优的。因此，总存在一个以贪心选择 开始的最优活动安排方案。
先选择，再得到子问题的解
动态规划的解题框架
贪心算法的解题框架
贪心算法的基本要素
• 贪心选择性质：所求问题的全局最优解可 以通过一系列局部最优的选择（即贪心选 择）来达到。
– 这是贪心算法与动态规划算法的主要区别。
• 最优子结构性质：当原问题的最优解包含 子问题的最优解时，称此问题具有最优子 结构性质。
n
i i
c
装满背包
max vi xi
i 1
X {x1 , x2 ,..., xn }
Xi ∈[0,1]
•
–
如何选择物品装入的优先级（贪心策略）？
价值贪心策略：优先选择价值最大的物品
• 如果所选择的物品重量很大，使得背包载重的消耗速度太快 不能保证目标函数的值快速增加
–
–
重量贪心策略：优先选择重量最小的物品
• 给定一个带权有向图G=(V,E)，每条边的权是一个 非负实数，还给定V中的一个顶点，称为源。计算 从源到所有其他顶点的最短路径长度（即路上各 边权之和）。
v0
10 v1 30 15 20
v2
10 v3
4 v4
10
• Dijkstra’s algorithm
首先证明原问题的一个最优解是以贪心选择开始。然后假设i次贪心选择能 够得到一个最优解，那么证明i+1次贪心选择也能得到一个最优解。
• 证明kna排序后依次选择物品直到装满背包， 能够得到问题的一个整体最优解。
i次贪心选择 非贪心策略所选 的结果 将原问题的一个最优解A按照量度标准排序 A={x1,
•
价值重量比策略：将物品按单位重量价值降序排序， 从第一项开始装背包，然后是第二项，依此类推，尽 可能的多放，直到装满背包。
• 优先选择既使目标函数的值增加最快，又使背包载重的消耗 较慢的物品
• knapsack_greedy算法：选择物品单位重量的价值 作为物品装入的优先级
1. 计算每种物品单位重量的价值vi / wi O(n) 2. 将尽可能多的单位重量价值最高的物品装入背包 O(nlogn)
贪心算法的正确性证明
• 证明每一步所做的贪心选择最终能够得到问题的 一个整体最优解。
– 首先证明问题的一个最优解以贪心选择开始。
贪心选择 • 考察问题的一个整体最优解，并证明可修改这个最优解，使其 以贪心选择开始。// 例如活动安排问题中，B = A - {ek}∪{e1} 性质
– 进一步证明做了贪心选择后，原问题的最优解包含了 子问题的最优解。
• 活动安排问题就是要在所给的活动集合中选出最大的相容 活动子集合。
反例
• 贪心选择策略
– – – – – 选择具有最早开始时间的活动？ 选择具有最早结束时间的活动？ 选择具有最少占用时间的活动？ 选择覆盖未选择活动最少的活动？ ……
t
• 直观上，每次选择具有最早结束时间的相容活动，使剩余 的可安排时间段极大化，以便安排尽可能多的相容活动。
• 先假设由原问题的最优解导出的子问题的最优解不是最优的， 最优子结构 再说明在这个假设下可构造出比原问题最优解更好的解，从而 导致矛盾。//例如活动安排问题中，若A是原问题E的一个最优 性质 解，则A-{e1}是活动安排问题E’ = {i∈E: si≥f1}的一个最优解
– 然后，用数学归纳法证明，通过每一步贪心选择，最 终可得到问题的一个整体最优解。