[C8][Greedy] 贪婪算法

• 贪婪算法寻找局部最优解，近似获取全局最优解
• 对于NP完全问题，还没有找到快速解决方法，只能采用枚举所有可能性方式。因此，最佳做法是使用近似算法，例如贪婪算法
  • 旅行商过序列城市问题和集合覆盖问题
• 贪婪算法易于实现、运行速度快，是不错的近似算法

8.1 教室调度问题

早上9点到12点中间有5节课，每隔半小时开一门，每门课1小时，如何尽可能多的在一间教室上课。

贪婪解法：每步采用局部最优解 -> 得到全局最优解

• 选出当前结束最早的课，这是对一节课
• 接下来，必须选择上一节课结束后才能开始的课中，结束最早的课
• 重复上一步，直到结束

8.2 背包问题

假设一个小偷在商场中只能偷35磅重量的物品，如何选择？

• 本质：在有限空间内最大化价值？
• 贪婪解法：每次偷物品，选择重量允许情况下最贵的物品
• 存在问题：该解法可能无法获得最优解，但是简单易行，结果接近最优解

8.3 集合覆盖问题

找出全美50个州的最小广播集合，每个广播包含多个州地区？

• 常规解法：穷举所有广播台集合，有2^n个子集，找出覆盖全美50个州的最小集合，时间复杂度O(2^n)，时间太久
• 近似算法（贪婪算法 O(n^2)）：
  • 选出一个广播台，即覆盖了最多的目前还未覆盖的州，即使包含重复州也没关系 O(n)
  • 重复上一步，直到覆盖了所有州 O(n)

判断近似算法优劣标准

• 速度有多快
• 得到的近似解与最优解的接近程度

Python解法

states_needed = {'az', 'ca', 'id', 'mt', 'nv', 'or', 'ut', 'wa'}
stations = {
    'kone': {'id', 'nv', 'ut'},
    'ktwo': {'id', 'mt', 'wa'},
    'kthree': {'ca', 'nv', 'or'},
    'kfour': {'nv', 'ut'},
    'kfive': {'az', 'ca'}}
final_stations = set()
while states_needed:
    best_station = None
    most_states_covered = set()
    for station, states_for_station in stations.items():
        covered = states_needed & states_for_station    # 计算集合交集
        if len(covered) > len(most_states_covered):
            best_station = station
            most_states_covered = covered
    final_stations.add(best_station)
    states_needed -= most_states_covered
print(final_stations)

集合操作

• 并集：集合合并
• 交集：找出两个集合中共有元素
• 差集：A - B 表示从A集合中剔除出现在B集合中的元素

8.4 NP完全问题

• P类问题（polynominal）：存在多项式时间算法的问题
• NP问题（Nondeterministic polynominal，非确定性多项式）能在多项式时间内验证得出一个正确解的问题，但不知道这个问题是否存在多项式时间算法，例如旅行家推销问题travelling salesman problem
• NPC类问题（Nondeterminism Polynomial complete）存在一个NP问题，所有的NP问题都可以约化成它：
  • 证明这是一个NP问题
  • 证明其中一个已知的NPC问题能约化到它

旅行商问题

一个旅行商需要经过5个城市，起点未知，求解最短路径？

• 这是一个NPC问题，计算所有可能路径是阶乘函数n!

旅行商问题和集合覆盖问题共同之处：

• 需要计算所有的解，并从中选出最小/最短的那个
• 属于NPC问题

近似解法（贪婪）：**
随便选择一个城市，每次选择下一个城市时，选择未去城市中最近的城市，直到所有城市都去过。

NP完全问题是以难解著称的问题，例如旅行商问题和集合覆盖问题，很多聪明人认为，根本不能编写出可快速解决这些问题的算法，因此，通常使用贪婪近似算法解决。
**

如何识别NP完全问题

球员组建问题

• 教练提出球队必须具备要求：四分卫，跑卫，雨中做战，抗压
• 本质上是集合覆盖问题：即每次寻找能力当前球队没有的能力中覆盖最多的队员，直到队员数量上限

最短路径问题

• 当我们已知起始点和终点求最短路径时，可采用BFS，Dijkstra等算法
• 但是当我们无法确定起始点时，就是一个NP完全问题，需要使用近似算法求解，贪心思想

NP完全问题特征：

• 随着元素增加速度越来越慢
• 涉及所有组合问题
• 不能将问题拆分为小问题，必须考虑所有可能性
• 问题涉及序列（旅行商的城市序列）且难以解决
• 涉及集合（广播台集合）且难以解决
• 如果问题可以转化为集合覆盖问题或旅行商问题，则它一定是NPC问题