巴尔加瓦算法图解——第八章 贪婪算法（全局最优）（下）

前言

提前回来了，不过也是短暂地回来一下。之后更新的频率会慢一些，有毕业设计还有一些申请的事情要忙。

这五天拼尽全力了准备了某场考试。《请回答1988》这部剧赐予了我很多，狗焕形容自己失败的暗恋“搞怪的不是红绿灯，而是我数不清的犹豫”，宝拉说自己一心无法做两件事，在胶囊似的空间里学习熬过法考，在难受的时候想一下这些就更容易坚持下去。我并不是不知道怎样生活更享受更容易，只是一直以来的惯性让我什么都想拼到底。我也知道我的很多同学可以轻易地考到这个分数，甚至逼近满分，但我也知道对我而言Everything is set up for your next best season. 这就是我一直用尽全力的理由，每每想到这些真的不禁感叹自己是一个坚强又有恒心的人。

之后的日子里还是学着过轻松一点吧，感觉每天有哪个小时没学习，都好像有罪，这个心理状态其实不太健康。本来就在假期，为什么不能好好休息呢～

目录

8.3　集合覆盖问题

8.4　NP完全问题

---

8.3　集合覆盖问题

??集合类似于列表，只是不能包含重复的元素；

??你可执行一些有趣的集合运算，如并集、交集和差集。

如何找出覆盖全美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）是一种通过在每一步选择中都采取当前状态下最优（局部最优）的选择，从而希望最终能够达到全局最优解的算法。在每个步骤中，贪婪算法选择当前状态下的最佳解决方案，而不考虑整体的问题。

8.4　NP完全问题

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完全问题时，最佳的做法是使用近似算法。

??贪婪算法易于实现、运行速度快，是不错的近似算法。