Chapter 16 Greedy Algorithms

贪婪算法 Greedy Algorithms

• 与动态规划类似，但方法更简单

–也用于优化问题

• 想法：当我们有选择的时候，现在就做一个看起来最好的

–做出局部最优选择，希望获得全局最优解决方案

• 贪婪算法并不总是产生最优解

• 当问题具有某些一般特征时，贪婪算法给出最优解

选择活动 Activity Selection

• 计划n需要独占使用公共资源的活动 ——一套活动 【compatible（可共用的）】【overlap（重叠）】

活动选择问题 Activity Selection Problem

选择最大可能的不重叠（相互兼容）活动集。

例如：

• 活动按完成时间的递增顺序排序

• 相互兼容活动的子集： {a3, a9, a11}

• 相互兼容活动的最大集合：{a1, a4, a8, a11}和 {a2, a4, a9, a11}

最优子结构 Optimal Substructure

• 定义子问题的空间： –ai结束后开始和aj开始前完成的活动
• 与Sij中的活动兼容的活动

–fi完成的所有活动–不早于s开始的所有活动

代表问题 Representing the Problem

• 添加虚构的活动 在一组Sij中，我们假设活动按完成时间的递增顺序排序：
• 如果 i ≥ j发生了什么？
• 我们只需要考虑Sij的集合0≤ i<j≤ n+1

最优子结构 Optimal Substructure

• 子问题：–从集合Sij中选择相互兼容活动的最大规模子集

• 假设上述子问题的解决方案包括活动ak（Sij为非空）

递归解 Recursive Solution

• 任何最佳解决方案（与一组Sij相关）都包含子问题Sik和Skj的最佳解决方案

• c[i，j]=Sij中相互兼容活动的最大规模子集的规模

• 如果Sij= c[i，j]=0（i≥ j） 如果Sij 如果我们认为AK用于最优解（Sij的相互兼容活动的最大大小子集）

c[i，j]=c[i，k]+c[k，j]+1

• k有j–i–1个可能值

– k=i+1，…，j-1–ak不能是ai或aj

（根据Sij的定义

–我们检查所有的值并取最好的值

我们现在可以编写一个动态规划算法

定理 Theorem

然后：

1. am用于Sij相互兼容活动的某些最大规模子集 –存在一些包含am的最佳解决方案
2. Sim= – 选择am使Smj成为唯一的非空子问题

证明 Proof

证明：贪婪选择性质 Proof: Greedy Choice Property

1. am用于Sij相互兼容活动的某些最大规模子集

为什么这个定理有用？ Why is the Theorem Useful?

• 进行贪婪选择（Sij中完成时间最早的活动）

—减少子问题和选择的数量

–以自上而下的方式解决每个子问题

贪心法 Greedy Approach

• 要从集合Sij中选择相互兼容活动的最大大小子集，请执行以下操作：

–选择am∈ 最早完成时间的Sij（贪婪选择）

–将am添加到最佳解决方案中使用的活动集合中

–解决设置Smj的相同问题

• 根据定理

–通过选择am，我们保证使用了最佳解决方案中包含的活动

→ 在做出选择之前，我们不需要解决子问题Smj！

–问题具有贪婪选择特性

重构最优解 Reconstructing the Optimal Solution

• 项目4
• 项目2
• 项目1
• 从P（n，W）开始
• 当你向左转时→ 项目一已经完成
• 当你直走的时候→ 项目一尚未实施

最优子结构 Optimal Substructure

• 考虑最重的重量，最重的重量

• 如果我们从该负载中移除项目j

→ 剩余荷载必须是最有价值的荷载，最大重量 ，可从剩余n–1项中提取

重叠子问题 Overlapping Subproblems

例如：灰色显示的所有子问题可能取决于P（i-1，w）

Hw

考虑以下关于活动选择问题的变化。你有一个处理器，可以每天24小时运行。用户提交在处理器上运行日常作业的请求。每个这样的工作都有一个开始时间和一个结束时间；如果接受该作业在处理器上运行，则该作业必须在其开始时间和结束时间之间每天连续运行。（请注意，某些作业可以在午夜之前开始，午夜之后结束；这导致了一种不同于我们在活动选择问题中看到的情况。）

给定n个这样的作业的列表，您的目标是接受尽可能多的作业（无论其长度如何），但处理器在任何给定时间点最多只能运行一个作业。提供一个运行时间为多项式n的算法。为了简单起见，您可以假设没有两个作业具有相同的开始或结束时间。

实例考虑由开始时间、结束时间对指定的四个作业。（下午6点，上午6点），（下午9点，上午4点），（凌晨3点，下午2点），（下午1点，下午7点）。

最佳解决方案是选择两个作业（晚上9点，早上4点）和（下午1点，晚上7点），这两个作业可以安排得不重叠。

16.1-2

假设我们不总是选择第一个要完成的活动，而是选择与所有先前选择的活动兼容的最后一个要开始的活动。描述这种方法是一种贪婪算法，并证明它产生了一个最优解。

16.2-6

演示如何在O（n）时间内解决分数背包问题。