本章内容

学习如何处理不可能完成的任务：没有快速算法的问题（NP完全问题）。
学习识别NP完全问题，以免浪费时间去寻找解决它们的快速算法。
学习近似算法，使用它们可快速找到NP完全问题的近似解。
学习贪婪策略——一种非常简单的问题解决策略。

本章小结

贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。
对于NP完全问题，还没有找到快速解决方案。
面临NP完全问题时，最佳的做法是使用近似算法。
贪婪算法易于实现、运行速度快，是不错的近似算法。

本章练习

练习1

你在一家家具公司工作，需要将家具发往全国各地，为此你需要将箱子装上卡车。每个箱子的尺寸各不相同，你需要尽可能利用每辆卡车的空间，为此你将如何选择要装上卡车的箱子呢？请设计一种贪婪算法。使用这种算法能得到最优解吗？
- 贪心：每次装入都选择可装入且最大的箱子，直至卡车不能放下为止。贪心并不能保证全局最优解。
你要去欧洲旅行，总行程为7天。对于每个旅游胜地，你都给它分配一个价值———表示你有多想去那里看看，并估算出需要多长时间。你如何将这次旅行的价值最大化？请设计一种贪婪算法。使用这种算法能得到最优解吗？
- 贪心：不断挑选价值最大且剩余时间足够的地方，直至不能重复为止。贪心并不能保证全局最优解。

练习2
下面各种算法是否是贪婪算法。

快速排序。
- 不是。快速排序采用分而治之策略，其每一次的分治并没有体现出局部最优。
广度优先搜索。
- 是。
狄克斯特拉算法。
- 是
解释：

练习3

有个邮递员负责给20个家庭送信，需要找出经过这20个家庭的最短路径。请问这是一个NP完全问题吗？
- 是。
在一堆人中找出最大的朋友圈（即其中任何两个人都相识）是NP完全问题吗？
- 是。
你要制作美国地图，需要用不同的颜色标出相邻的州。为此，你需要确定最少需要使用多少种颜色，才能确保任何两个相邻州的颜色都不同。请问这是NP完全问题吗？
- 是。

8.1 教室调度问题

下图是目前的课程安排，但是你希望在这间教室上尽可能多的课。如何选出尽可能多且时间不冲突的课程呢？

贪心的解决办法

选出结束最早的课，它就是要在这间教室上的第一堂课。
接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。

用专业术语说，贪心的解决办法就是你每步都选择局部最优解，最终得到的就是全局最优解。显然贪心的结果并不保证是全局最优解，但是贪心的优点是算法简单。

8.2 背包问题

贪心并不是全局最优解

贪心会在第一次装包直接偷走音响，但是之后，背包已经不能再装下其他商品，所以偷走价值3000美金。但是实际上，我们知道其实可以偷走电脑和吉他，则可获得3500美金。显然贪心并不是全局最优解

8.3 集合覆盖问题

哪些时候？你只能采用贪心算法

举个广播公司的例子

有50个州，有多家广播公司，每个广播公司可能服务多个确定的多个州。你需要挑选出最小的广播公司的集合，来满足覆盖全国的广播。

先说结论：对于这个案例，求出全局最优解的时间复杂度太高，只能采用贪心算法。

采用枚举所有集合来找到全局最优解。这种情况，需要考虑所有的集合，并最终在所有集合中选择最小者。
- 很可惜，时间复杂度O(2 )，实在太大了。
采用近似算法，即可用贪心算法。
- 时间复杂度为O(n )，可以接受。其中n为广播台数量
- 算法思路如下：
  1. 选出这样一个广播台，即它覆盖了最多的还未覆盖的州。即便这个广播台覆盖了一些已覆盖的州，也没有关系。
  2. 重复第一步，直到覆盖了所有的州。

广播公司案例的贪心算法实现

# 传入一个数组，将其转换为集合，这个集合包含还未被覆盖的州。
    # 注意每次做出选择后需要修正这个集合。
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"]) 
# 这个集合用于存储最终选择的广播公司的集合。
final_stations = set() 
###
# 循环找出最优的选择（能够覆盖最多的还未覆盖的州的广播公司），直至states_neede为空 
while states_needed:
    best_station = None
    states_covered =set()
    for station,states in stations.items():
        covered = states & states_needed  # 该广播公司能够覆盖的还未覆盖的州的集合
        if len(states_covered) < len(covered):
            best_station = station
            states_covered = covered
    # 更新最终选择的广播公司的集合和所需覆盖的州的集合
           # 注意：final_stations += best_station 是错误的写法。集合有：交并差运算，但没有加。
        # 细节：已经被选择的广播公司，不可能在再被选中（见该代码：covered = states & states_needed）
    final_stations.add(best_station)
    states_needed -= states_covered

输出

8.4 NP 完全问题

NP完全问题的简单定义是，以难解著称的问题，如旅行商问题和集合覆盖问题。这类问题根本不可能编写出可快速解决这些问题的算法。

因此，对于NP完全问题，一般采用近似求解，比如贪心算法。

8.4.1 旅行商问题详解
这被称为阶乘函数（factorial function），假设有10个城市，可能的路线有多少条呢？10! = 3 628 800。因此，如果涉及的城市很多，根本就无法找出旅行商问题的正确解。

启示：旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小/最短的那个。这两个问题都属于NP完全问题。

旅行社问题的近似求解，采用贪心：

随便选择出发城市，然后每次选择要去的下一个城市时，都选择还没去的最近的城市。

8.4.2 如何识别 NP 完全问题

简单理解:涉及序列、集合、组合等问题，且时间复杂度高，又规模不可缩小。

算法图解

8章贪婪算法

本章内容

本章小结

本章练习