算法学习(6)：贪心算法
教室调度问题
假设有如下课程表，你希望将尽可能多的课程安排在某间教室上。
你希望在这间教室上尽可能多的课。如何选出尽可能多且时间不冲突的课程呢？
这个问题好像很难，不是吗？实际上，算法可能简单得让你大吃一惊。具体做法如下。
(1) 选出结束最早的课，它就是要在这间教室上的第一堂课。
(2) 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。
因此将在这间教室上如下三堂课。
显然，贪婪算法就是你每步都选择局部最优解，最终得到的就是全局最优解。
但是这种贪心策略每次都好用吗？
背包问题
假设你是个贪婪的小偷，背着可装35磅（1磅≈0.45千克）重东西的背包，在商场伺机盗窃各种可装入背包的商品。
你力图往背包中装入价值最高的商品，你会使用哪种算法呢？
同样，你采取贪婪策略，这非常简单。
- 盗窃可装入背包的最贵商品。
- 再盗窃还可装入背包的最贵商品，以此类推。
只是这次这种贪婪策略不好使了！例如，你可盗窃的商品有下面三种。
你的背包可装35磅的东西。音响最贵，你把它给偷了，但背包没有空间装其他东西了。
你偷到了价值3000美元的东西。且慢！如果不是偷音响，而是偷笔记本电脑和吉他，总价将为3500美元！
在这里， 贪婪策略显然不能获得最优解，但非常接近。下一章将介绍如何找出最优解。不过小偷去购物中心行窃时，不会强求所偷东西的总价最高，只要差不多就行了。
从这个示例你得到了如下启示：在有些情况下，完美是优秀的敌人。有时候，你只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。
问题1：
你在一家家具公司工作，需要将家具发往全国各地，为此你需要将箱子装上卡车。每个箱子的尺寸各不相同，你需要尽可能利用每辆卡车的空间，为此你将如何选择要装上卡车的箱子呢？请设计一种贪婪算法。使用这种算法能得到最优解吗？
解答：
一种贪婪策略是，选择可装入卡车剩余空间内的最大箱子，并重复这个过程，直到不184 练习答案能再装入箱子为止。使用这种算法不能得到最优解。
问题1：
你要去欧洲旅行，总行程为7天。对于每个旅游胜地，你都给它分配一个价值——表示你有多想去那里看看，并估算出需要多长时间。你如何将这次旅行的价值最大化？请设计一种贪婪算法。使用这种算法能得到最优解吗？
解答：
不断地挑选可在余下的时间内完成的价值最大的活动，直到余下的时间不够完成任何活动为止。使用这种算法不能得到最优解。
集合覆盖问题
假设你办了个广播节目，要让全美50个州的听众都收听得到。为此，你需要决定在哪些广播台播出。在每个广播台播出都需要支付费用，因此你力图在尽可能少的广播台播出。现有广播台名单如下。
每个广播台都覆盖特定的区域，不同广播台的覆盖区域可能重叠。
如何找出覆盖全美50个州的最小广播台集合呢？听起来很容易，但其实非常难。具体方法如下。
(1) 列出每个可能的广播台集合，这被称为幂集（power set） 。可能的子集有2 ^ N个。
(2) 在这些集合中，选出覆盖全美50个州的最小集合。
问题是计算每个可能的广播台子集需要很长时间。由于可能的集合有个，因此运行时间为O(
)。如果广播台不多，只有5～10个，这是可行的。但如果广播台很多，结果将如何呢？随着广播台的增多，需要的时间将激增。假设你每秒可计算10个子集，所需的时间将如下。
没有任何算法可以足够快地解决这个问题！怎么办呢？
用贪婪算法可化解危机！使用下面的贪婪算法可得到非常接近的解。
(1) 选出这样一个广播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖的州，也没有关系。
(2) 重复第一步，直到覆盖了所有的州。
这是一种近似算法（approximation algorithm） 。在获得精确解需要的时间太长时，可使用近似算法。判断近似算法优劣的标准如下：
- 速度有多快；
- 得到的近似解与最优解的接近程度。
贪婪算法是不错的选择，它们不仅简单，而且通常运行速度很快。在这个例子中，贪婪算法的运行时间为O()，其中n为广播台数量。
旅行商问题
有一位旅行商，他需要前往5个城市。
这位旅行商（姑且称之为Opus吧）要前往这5个城市，同时要确保旅程最短。为此，可考虑前往这些城市的各种可能顺序。
对于每种顺序，他都计算总旅程，再挑选出旅程最短的路线。 5个城市有120种不同的排列方式。因此，在涉及5个城市时，解决这个问题需要执行120次操作。涉及6个城市时，需要执行720次操作（有720种不同的排列方式）。涉及7个城市时，需要执行5040次操作！
推而广之，涉及n个城市时，需要执行n!（n的阶乘）次操作才能计算出结果。因此运行时间为O(n!)，即阶乘时间。除非涉及的城市数很少，否则需要执行非常多的操作。如果涉及的城市数超过100，根本就不能在合理的时间内计算出结果——等你计算出结果，太阳都没了。
有的人可能认为为什么不用Dijkstra算法，可能你还没搞明白，
- Dijkstra算法是求两个点之间的最短路径的算法
- 而这里是求要遍历所有顶点而路径最短的算法
怎么解决呢？
我会采取这样的做法：随便选择出发城市，然后每次选择要去的下一个城市时，都选择还没去的最近的城市。假设旅行商从马林出发。
总旅程为71英里。这条路径可能不是最短的，但也相当短了。
像旅行商问题，广播覆盖问题，都一些共同之处：
你需要计算所有的解，并从中选出最小/最短的那个。这两个问题都属于NP完全问题。
如何识别 NP 完全问题
Jonah正为其虚构的橄榄球队挑选队员。他列了一个清单，指出了对球队的要求：优秀的四分卫，优秀的跑卫，擅长雨中作战，以及能承受压力等。他有一个候选球员名单，其中每个球员都满足某些要求。
Jonah需要组建一个满足所有这些要求的球队，可名额有限。等等， Jonah突然间意识到，这不就是一个集合覆盖问题吗！
Jonah可使用前面介绍的近似算法来组建球队。
(1) 找出符合最多要求的球员。
(2) 不断重复这个过程，直到球队满足要求（或球队名额已满）。
NP完全问题无处不在！如果能够判断出要解决的问题属于NP完全问题就好了，这样就不用去寻找完美的解决方案，而是使用近似算法即可。但要判断问题是不是NP完全问题很难，易于解决的问题和NP完全问题的差别通常很小。例如，连个点之间的最短路径，你知道如何找出从A点到B点的最短路径。
但如果要找出经由指定几个点的的最短路径，就是旅行商问题——NP完全问题。简言之，没办法判断问题是不是NP完全问题，但还是有一些蛛丝马迹可循的。
- 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
- 涉及“所有组合”的问题通常是NP完全问题。
- 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
- 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
- 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
- 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。