《算法图解》学习笔记习题和代码（第八章 贪婪算法）Python3
目录
第八章 贪婪算法
学习如何处理不可能完成的任务：没有快速算法的问题（NP完全问题）。
学习识别NP完全问题，以免浪费时间去寻找解决它们的快速算法。
学习近似算法，使用它们可快速找到NP完全问题的近似解。
学习贪婪策略——一种非常简单的问题解决策略。
8.1 教室调度问题
有如下课程表，你希望将尽可能多的课程安排在某间教室上。
发现没有办法让这些课都在这间教室上 ，因为时间有冲突。
如何选出尽可能多且时间不冲突的课程呢？ 这个解决方法很简单。
具体做法如下。
(1) 选出结束最早的课，它就是要在这间教室上的第一堂课。
(2) 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。
重复这样做就能找出答案！
这个算法容易、显而易见。但这正是贪婪算法的优点——简单易行！贪婪算法很简单：每步都采取最优的做法。
在这个示例中，你每次都选择结束最早的课。用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。信不信由你，对于这个调度问题，上述简单算法找到的就是最优解！
显然，贪婪算法并非在任何情况下都行之有效，但它易于实现！下面再来看一个例子。
8.2 背包问题
假设你是个贪婪的小偷，背着可装35磅（1磅≈0.45千克）重东西的背包，在商场伺机盗窃各种可装入背包的商品。 你力图往背包中装入价值最高的商品，你会使用哪种算法呢？ 同样使用贪婪算法，很简单。
贪婪策略，非常简单。
(1) 盗窃可装入背包的最贵商品。
(2) 再盗窃还可装入背包的最贵商品，以此类推。
下图是可以偷的东西。
根据贪婪算法，我们先偷最贵的音响，但是装了音响，背包就没有地方装别的东西了。（35磅的容量）此时你共偷到了3000美元的东西。
但是如果你不投音响，而是偷笔记本电脑+吉他，重量一共35磅，背包可以装下，总价值为3500美元，价值更高。
在这个示例中，贪婪算法就不能获得最优解了，但非常接近。
从这个示例你得到了如下启示：在有些情况下，完美是优秀的敌人。有时候，你只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。
练习1
8.1 你在一家家具公司工作，需要将家具发往全国各地，为此你需要将箱子装上卡车。每个箱子的尺寸各不相同，你需要尽可能利用每辆卡车的空间，为此你将如何选择要装上卡车的箱子呢？请设计一种贪婪算法。使用这种算法能得到最优解吗？
答：按箱子大小装，先把最大的箱子装上卡车，以此类推。或者按箱子的长边或短边大小进行先后装箱。
参考答案：一种贪婪策略是，选择可装入卡车剩余空间内的最大箱子，并重复这个过程，直到不能再装入箱子为止。使用这种算法不能得到最优解。
8.2 你要去欧洲旅行，总行程为7天。对于每个旅游胜地，你都给它分配一个价值——表示你有多想去那里看看，并估算出需要多长时间。你如何将这次旅行的价值最大化？请设计一种贪婪算法。使用这种算法能得到最优解吗？
答：先按喜欢程度给每个旅游地点分配价值，并同时估算游玩时间。再根据价值排序进行调整，限定时间在7天以内。
参考答案：不断地挑选可在余下的时间内完成的价值最大的活动，直到余下的时间不够完成任何活动为止。使用这种算法不能得到最优解。
8.3 集合覆盖问题
办一个广播节目，要让全美50个州的听众都收听得到，需要决定在哪些广播台播出。每个广播台播出都需要支付费用，因此你力图在尽可能少的广播台播出。现有广播台名单如下。
每个广播台都覆盖特定的区域，不同广播台的覆盖区域可能重叠。
如何找出覆盖全美50个州的最小广播台集合呢？
(1) 列出每个可能的广播台集合，这被称为幂集（power set）。可能的子集有个。 幂集的概念。
幂集：原集合中所有的子集（包括全集和空集）构成的集族。
(2) 在这些集合中，选出覆盖全美50个州的最小集合。
计算每个可能的广播台子集需要很长时间。由于可能的集合有个，因此运行时间为O(
)。假设你每秒可计算10个子集，所需的时间将如下。
没有任何算法可以足够快地解决这个问题！怎么办呢？
使用贪婪算法!
近似算法
贪婪算法可化解危机！使用下面的贪婪算法可得到非常接近的解。
(1) 选出这样一个广播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖
的州，也没有关系。
(2) 重复第一步，直到覆盖了所有的州。
这是一种近似算法（approximation algorithm）
代码
出于简洁考虑，假设要覆盖的州没那么多。
1.准备工作
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) #需要覆盖的州可供选择的广播台清单，及广播台覆盖的州，使用散列表来表示它。键为广播台的名称，值为广播台覆盖的州。
stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"]) #这里共5个广播台最后，需要使用一个集合来存储最终选择的广播台。
final_stations = set() #存储最终选择的广播台2.计算答案
下图是5个广播台和他们的覆盖范围。
根据前面对这个问题分析的近似算法，我们需要遍历所有的广播台，从中选择覆盖了最多的未覆盖州的广播台。我将这个广播台存储在best_station中。
best_station = None
states_covered = set() #set() 转化为集合，确保集合里没有重复元素
for station, states_for_station in stations.items(): #广播台及覆盖的州
covered = states_needed & states_for_station #需要覆盖的州和该广播台覆盖的州 ，&计算交集
if len(covered) > len(states_covered): #计算交集
best_station = station
states_covered = covered
final_stations.add(best_station)covered是 一 个 集 合 ， 包 含 同 时 出 现 在 states_needed和 states_for_station中的州；它包含当前广播台覆盖的
一系列还未覆盖的州！接下来，你检查该广播台覆盖的州是否比best_station多。 如果是这样的，就将best_station设置为当前广播台。最后，你在for循环结束后将best_station添加到最终的广播台列表中。 final_stations.add(best_station)
还需更新states_needed。由于该广播台覆盖了一些州，因此不用再覆盖这些州。 states_needed -= states_covered 你不断地循环，直到states_needed为空。这个循环的完整代码如下。
best_station = None
states_covered = set()
while states_needed:
best_station = None
states_covered = set() #set() 转化为集合，确保集合里没有重复元素
for station, states in stations.items(): #广播台及覆盖的州
covered = states_needed & states #需要覆盖的州和该广播台覆盖的州 ，&计算交集
if len(covered) > len(states_covered):
best_station = station
states_covered = covered #一次for 循环用于寻找 覆盖needed州最多的广播台。station_needed也在不断更新
states_needed -= states_covered
final_stations.add(best_station)
print(final_stations)OUT: {'kthree', 'kfive', 'ktwo', 'kone'}
可以发现这4个广播台覆盖了所有州。
从所有广播台找出一个覆盖州最多的广播台，，再更新station_needed（需要覆盖的州随广播台增加而减少）
再从所有广播台中找出一个需要覆盖的剩下的州中覆盖最多的广播台，依次循环。
练习2
下面各种算法是否是贪婪算法。
8.3 快速排序。 答：不是
8.4 广度优先搜索。 答：是
8.5 狄克斯特拉算法。 答：是
快速排序是根据基线条件，再划分，进行递归，每次都没有找到最优值。
广度优先搜索，狄克斯特拉算法都是从周围节点中优先找到代价最小的，更新邻居代价，再重复这个过程。（计算所有的解，找到代价最小的）
8.4 NP 完全问题
8.4.1 旅行商问题详解
这一章讲的贪婪算法，和第一章的旅行商问题都是NP完全问题。
旅行商问题：
旅行商需要前往5个不同的城市。他需要找出前往这5个城市的最短路径，为此，必须计算每条可能的路径。
前往5个城市时，可能的路径有多少条呢？ 5！=120条
（5个城市都可以作为起点，接着另外四个城市都可以作为第二个去的城市，以此类推。。。共5x4x3x2x1=120条路径）
10个城市呢？10！这被称为阶乘函数（factorial function）。
旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小/最短的那个。这两个问题都属于NP完全问题。
8.4.2 如何识别NP 完全问题
又举了一个NP完全问题的例子:
Jonah要组建橄榄球队，对队员有要求：优秀的四分卫，优秀的跑卫，擅长雨中作战，以及能承受压力等。并且还有一些人员清单，包含他们的特质：
想组建一个满足所有这些要求的球队，可名额有限。这就是一个集合覆盖问题！
Jonah可使用前面介绍的近似算法来组建球队。
(1) 找出符合最多要求的球员。
(2) 不断重复这个过程，直到球队满足要求（或球队名额已满）。
判断NP完全问题：
元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
涉及“所有组合”的问题通常是NP完全问题。
不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。
练习3
8.6 有个邮递员负责给20个家庭送信，需要找出经过这20个家庭的最短路径。请问这是一个NP完全问题吗？
8.7 在一堆人中找出最大的朋友圈（即其中任何两个人都相识）是NP完全问题吗？
8.8 你要制作美国地图，需要用不同的颜色标出相邻的州。为此，你需要确定最少需要使用多少种颜色，才能确保任何两个相邻州的颜色都不同。请问这是NP完全问题吗？
答：是；是；是 （都是没有捷径可走的问题，需要考虑每种情况）
8.5 小结
贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。
对于NP完全问题，还没有找到快速解决方案。
面临NP完全问题时，最佳的做法是使用近似算法。
贪婪算法易于实现、运行速度快，是不错的近似算法。
下一篇： 许愿墙—许下你的愿望