算法图解——读书笔记07

贪婪算法

1 教室调度问题
假设有如下课程表，你希望将尽可能多的课程安排在某间教室上。

你没法上这些课都在这间教室上，因为有些课的上课时间有冲突。

解决方法如下：
1）选出结束最早的课，它就是要在这间教室上的第一堂课。
2）接下来，必须选择第一堂课结束后才开始的课，同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。重复这样做就能找出答案！下面来试试，美术课的结束时间最早，，为10:00 a.m.，因此它就是第一堂课。

接下来的课必须在10:00 a.m.后开始，且结束得最早。

以此类推，因此将在这件教室上如下三节课

很多人 说这个算法太容易，太显而易见，肯定不对。但这正是贪婪算法的优点——简单易行！贪婪算法很简单：每一步都采取最优解的做法。在这个示例中，你每次都选择结束最早的课，用专业术语说，就是你每一步都选择局部最优解，最终得到的就是全局最优解。
但是显然，贪婪算法并非在任何情况下都行之有效，但是它易于实现！下面再来看一个例子
2 背包问题
假设你是个贪婪的小偷，背着可装35磅（1磅≈0.45千克）重东西的背包，在商场伺机盗窃各种可装入背包的商品。
你力图往背包中装入价值最高的商品，你会使用哪种算法呢？

同样，你采取贪婪策略，这非常简单。
(1) 盗窃可装入背包的最贵商品。
(2) 再盗窃还可装入背包的最贵商品，以此类推。
只是这次这种贪婪策略不好使了！例如，你可盗窃的商品有下面三种。

你的背包可装35磅的东西。音响最贵，你把它给偷了，但背包没有空间装其他东西了。

你偷到了价值3000美元的东西。且慢！如果不是偷音响，而是偷笔记本电脑和吉他，总价将为3500美元！

在这里，贪婪策略显然不能获得最优解，但非常接近。
不过小偷去购物中心行窃时，不会强求所偷东西的总价最高，只要差不多就行了。从这个示例你得到了如下启示：在有些情况下，完美是优秀的敌人。有时候，你只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。

下面来看最后一个例子，在这个例子中，你别无选择，只能用贪婪算法。
假设你办了个广播节目，要让全美50个州的听众都收听得到。为此，你需要决定在哪些广播台播出。在每个广播台播出都需要支付费用，因此你力图在尽可能少的广播台播出。现有广播台名单如下。

每个广播台都覆盖特定的区域，不同广播台的覆盖区域可能重叠。

具体方法如下。
贪婪算法可化解危机！使用下面的贪婪算法可得到非常接近的解。
(1) 选出这样一个广播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖的州，也没有关系。
(2) 重复第一步，直到覆盖了所有的州。这是一种近似算法 （approximation algorithm）。
在获得精确解需要的时间太长时，可使用近似算法。判断近似算法优劣的标准如下：
速度有多快；
得到的近似解与最优解的接近程度。
贪婪算法是不错的选择，它们不仅简单，而且通常运行速度很快。在这个例子中，贪婪算法的运行时间为O (n 2 )，其中n 为广播台数量。

选择的广播台可能是2、3、4和5，而不是预期的1、2、3和5。下面来比较一下贪婪算法和精确算法的运行时间。

4　NP完全问题
NP完全问题的简单定义是，以难解著称的问题，如旅行商问题和集合覆盖问题。很多非常聪明的人都认为，根本不可能编写出可快速解决这些问题的算法。

如何识别NP完全问题
我们为什么会关注到NP完全问题的识别这个问题呢？若我们能识别出一个问题是NP完全问题，那么我们就可以用近似求解的方法去解决这个问题，而不用再去费力去求解完美解了。尽管我们没有办法判断某个问题是不是NP完全问题，但是还是有一些蛛丝马迹可引导我们做出判断：
（1）元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢；
（2）涉及“所有组合”的问题通常是NP完全问题；
（3）不能将问题分成小问题，必须考虑各种可能的情况，这可能是NP完全问题；
（4）如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题；
（5）如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题；
（6）如果问题可转换为集合覆盖问题或旅行商问题，那它肯定就是NP完全问题。

总结：
贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。
对于NP完全问题，还没有找到快速解决方案。
面临NP完全问题，最佳的做法是使用近似算法。
贪婪算法易于实现、运行速度快，是不错的近似算法。