前言
提前回来了，不过也是短暂地回来一下。之后更新的频率会慢一些，有毕业设计还有一些申请的事情要忙。
这五天拼尽全力了准备了某场考试。《请回答1988》这部剧赐予了我很多，狗焕形容自己失败的暗恋“搞怪的不是红绿灯，而是我数不清的犹豫”，宝拉说自己一心无法做两件事，在胶囊似的空间里学习熬过法考，在难受的时候想一下这些就更容易坚持下去。我并不是不知道怎样生活更享受更容易，只是一直以来的惯性让我什么都想拼到底。我也知道我的很多同学可以轻易地考到这个分数，甚至逼近满分，但我也知道对我而言Everything is set up for your next best season. 这就是我一直用尽全力的理由，每每想到这些真的不禁感叹自己是一个坚强又有恒心的人。
之后的日子里还是学着过轻松一点吧，感觉每天有哪个小时没学习，都好像有罪，这个心理状态其实不太健康。本来就在假期，为什么不能好好休息呢～
目录
??集合类似于列表，只是不能包含重复的元素；
??你可执行一些有趣的集合运算，如并集、交集和差集。
如何找出覆盖全美50个州的最小广播台集合？
（1）列出集合
每个位置都有“选”或者“不选”两个选择，总共有2^n种方案。
运行时间O（2^n），运行时间很慢。
（2）找最小。
近似算法：
（1）首先选择覆盖最多州的广播电台，然后进行循环，选出去除已覆盖州后，覆盖最多未覆盖州的广播台。
（2）重复（1）
这是一种近似算法(approximation algorithm)。在获得精确解需要的时间太长时，可使用近似算法。
判断近似算法优劣的标准如下：??速度有多快；??得到的近似解与最优解的接近程度。
贪婪算法是不错的选择，它们不仅简单，而且通常运行速度很快。在这个例子中，贪婪算法的运行时间为O(n^2)，其中n为广播台数量。
最好的情况：一个电台覆盖50个州，搜索一次。
最坏的情况：每个电台之间覆盖没有交集。第一次搜索规模是n，搜索N次，n^2。
代码：
def greedy_algorithm(states, stations):
??? final_stations = set()
??? while states:
??????? best_station = None
??????? states_covered = set()
??????? for station, state_coverage in stations.items():
??????????? covered = states & state_coverage
??????????? if len(covered) > len(states_covered):
??????????????? best_station = station
??????????????? states_covered = covered
??????? final_stations.add(best_station)
??????? states -= states_covered
??? return final_stations
# 示例数据
states = {"state1", "state2", "state3", "state4", "state5"}
stations = {
??? "station1": {"state1", "state2", "state3"},
??? "station2": {"state2", "state4"},
??? "station3": {"state1", "state4", "state5"}
}
# 运行贪婪算法
result = greedy_algorithm(states, stations)
# 输出结果
print("选择的广播电台:", result)贪婪算法时间vs精确算法时间比较：
| 广播台数量 | 精确算法时间（2^n） | 贪婪算法时间（n^2） |
| 5 | 3.2s | 2.5s |
| 10 | 102.4s | 10s |
| 32 | 13.6y | 102.4s |
| 100 | 4*10^21y | 16.67min |
下面各种算法是否是贪婪算法。
8.3 快速排序。否。（分治，不断将问题缩小规模）
8.4 广度优先搜索。是。（找最小路径）
8.5 狄克斯特拉算法。是。（找最优节点）
贪婪算法（Greedy Algorithm）是一种通过在每一步选择中都采取当前状态下最优（局部最优）的选择，从而希望最终能够达到全局最优解的算法。在每个步骤中，贪婪算法选择当前状态下的最佳解决方案，而不考虑整体的问题。
Non-deterministic Polynomial??非确定性多样式
这被称为阶乘函数(factorial function)，第3章介绍过。5!=120。假设有10个城市，可能的路线有多少条呢？10!=3628800。换句话说，涉及10个城市时，需要计算的可能路线超过300万条。正如你看到的，可能的路线数增加得非常快！因此，如果涉及的城市很多，根本就无法找出旅行商问题的正确解。旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小/最短的那个。这两个问题都属于NP完全问题。
近似求解
??元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。??涉及“所有组合”的问题通常是NP完全问题。
??不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
??如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
??如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
??如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。
练习8.6 有个邮递员负责给20个家庭送信，需要找出经过这20个家庭的最短路径。请问这是一个NP完全问题吗？?是
8.7 在一堆人中找出最大的朋友圈（即其中任何两个人都相识）是NP完全问题吗？是
8.8 你要制作美国地图，需要用不同的颜色标出相邻的州。为此，你需要确定最少需要使用多少种颜色，才能确保任何两个相邻州的颜色都不同。请问这是NP完全问题吗？?是
Np-completeness basics (longest simple path)
Polynomial（多项式）-time algorithms
Worst case running time: O(n^k) for some constant(常数)
There are some problems that cannot be in O(n^k) time.
Loosely speaking, such problems are called “NP-complete” problems
Polynomial: class of problems that are solvable in polynomial time
Np- class of problems that are?“verifiable” in polynomial time
（verify the certificate is correct in polynomial time）
8.5 小结
??贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。
??对于NP完全问题，还没有找到快速解决方案。
??面临NP完全问题时，最佳的做法是使用近似算法。
??贪婪算法易于实现、运行速度快，是不错的近似算法。