4.2
算法图解笔记——Chapter 8 greedy Algorithm
Author: Seven Zou
Email: aaa@qq.com
Language: Python2.7
8 贪婪算法
本章学习贪婪算法，这与自身的研究方向有些交叉，恰好利用这次学习来仔细研究一下算法。在优化问题中，背包问题、调度问题、集合覆盖问题等都属于经典问题。
8.1 教师调度问题
假设有如下课程表，希望将尽可能多的课程安排在某间教室上。这里就要同时考虑尽可能多且时间不冲突的课程。
针对算法逻辑如下：
- 1.选出结束最早的课，它就是要在这间教室上的第一堂课；
- 2.必须选择第一堂课结束后才开始的课。同样，选择结束最早的课，这将是要在这间教室上的第二堂课；
- 3.重复以上操作。
这就是贪婪算法的逻辑，每步都采取最优的做法。在优化中，也称为*每步都选择局部最优解，最终推广到全局最优解。
8.2 背包问题
假设你是个小偷，背着可装35磅物品的背包。目的是往背包中装入价值最高的物品。针对此问题逻辑可有：
- 窃取可装入背包的最贵商品；
- 再窃取还可装入背包的最贵商品。
- 重复操作。
但还需考虑重量问题。所以此时便不能获得最优解，而是近似最优解。
8.3 集合覆盖问题
假设有广播节目，要让全美50个州的听众都收听得到。需要决定在哪些广播台播出但同时广播台都需收取费用。
每个广播台都覆盖特定的区域，不同的广播台的覆盖区域可能重叠。
那么问题就转换成：如何找出覆盖全美50个州的最小广播台集合。那么算法的逻辑可以为：
- 列出每个可能的广播台集合，这称为幂集(power set)。可能的子集有个
- 在这些集合中，选出覆盖全美50个州的最小集合。
那么问题出现了，这个执行逻辑下的运行时间是。如果广播台不多，可以执行，但是一旦很多，那么需要的时间就会急剧增加。
近似算法
针对上述情况，使用贪婪算法可以得到非常接近的解。
- 选出这样的一个广播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖的州，也没有关系。
- 重复第一步，直到覆盖了所有的州。
这是一种近似算法(approximation algorithm)。判断算法的标准：1.执行速度；2.得到的近似解与最优解的接近程度。下面给出code。
# 准备工作
# 首先，创建一个列表，其中包含要覆盖的州
states_needed = set(["mt", "wa", "or", "id", "nv", "ut"， "ca", "az"]) # 传入一个数组，转换为集合
# 使用集合来表示要覆盖的州，集合类似于列表，集合不能包含重复的元素，则假设有
arr = [1, 2, 2, 3, 3, 3]
set(arr) # 转换为集合
# 创建可供选择的广播台清单
stations = {}
station["kone"] = set(["id", "nv", "ut"])
station["ktwo"] = set(["wa", "id", "mt"])
station["kthree"] = set(["or", "nv", "ca"])
station["kfour"] = set(["nv", "ut"])
station["kfive"] = set(["ca", "az"])
final_stations = set() # 创建一个集合存储最终选择的广播台
# 计算答案
# 正解可能有多个，需要遍历所有的广播台并从中选择覆盖了最多的未覆盖的广播台。
while states_needed:
best_station = None # 将这个覆盖了最多的未覆盖的广播台存储在best_station 中
states_covered = set() # 集合：包含该广播台覆盖的所有未覆盖的州
for station, states_for_station in station.items(): # 循环每个广播台，并确定它是否是最佳的广播台
covered = states_needed & states_for_station # 计算并集：两个集合合并
if len(covered) > len(states_covered): # 计算交集
best_station = station
states_covered = covered
states_needed -= states_covered # 更新states_needed 由于该广播台覆盖了一些州，因此不用再覆盖这些州
final_stations.add(best_station) # 将best_station添加入最终的广播台列表中
print final_stations
Output: set(['ktwo', 'kthree', 'kone', 'kfive'])
8.4 NP完全问题
解决集合覆盖问题，就必须计算每个可能的集合。那这于TSP问题又很相似。针对TSP问题，涉及到n个城市，就会有条路线。(第3章)，这称为阶乘函数(factorial function)。对于TSP问题和集合覆盖问题共同之处在于：你需要计算所有的解，并从中选出最小/最短的那个。这两个问题都属于NP完全问题。
NP完全问题的简单定义为，以难解著称的问题，如TSP问题和集合覆盖问题。很多非常聪明的人都认为，根本不可能编写出可快速解决这些问题的算法。针对这类问题我们只能去求解它的近似解。
对于NP完全问题如何识别：
-元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢；
-不能将问题分成小问题，必须考虑各种可能的可能。这可能是NP完全问题。
-如果问题涉及序列(如TSP问题中的城市序列)且难以解决，这可能是NP完全问题。
-如果问题设计集合(如广播台集合)且难以解决，这可能是NP完全问题。
-如果问题可转换为集合覆盖问题或TSP问题，那肯定是NP完全问题。
贪婪算法寻找局部最优，最终以此方式来获得全局最优；
对于NP完全问题，还没有找出快速解决方案；
针对NP完全问题，最佳的做发是使用近似算法；
贪婪算法易于实现、运行速度快。
Reference
[美]Aditya Bhargava/袁国忠, 算法图解, 北京：人民邮电出版社, 2017.3.
附个人Github地址: https://github.com/shiqi0404/Algorithm_Diagram，其中包括笔记、Code还有书本pdf版。