贪婪算法

  • 教室调度问题
  • 背包问题
  • 集合覆盖问题
  • NP完全问题

教室调度问题

假设有如下课程，要尽可能多地将它们安排在一间教室上：

课程 开始时间 结束时间
美术 9:00 10:00
英语 9:30 10:30
数学 10:00 11:00
计算机 10:30 11:30
音乐 11:00 12:00

贪婪算法的做法：

  1. 选出结束最早的课，它就是要在这间教室上的第一堂课（美术 9:00-10:00）
  2. 在与已选课不冲突的课中，选出结束最早的课（数学 10:00-11:00）
  3. 重复，选出音乐 11:00-12:00

这个贪婪策略得到了最优解。贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。

背包问题

假设你是个贪婪的小偷，背着可装 35 磅重东西的背包，可盗窃的商品有：

  • 音响：30 磅，3000 美元
  • 笔记本电脑：20 磅，2000 美元
  • 吉他：15 磅，1500 美元

贪婪策略：先偷最贵的（音响 3000 美元），但背包没有空间装其他东西了。然而偷笔记本电脑和吉他的总价为 3500 美元！贪婪策略显然不能获得最优解。

启示：在有些情况下，完美是优秀的敌人。有时候只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。

集合覆盖问题

假设你办了个广播节目，要让全美 50 个州的听众都收听得到，需要决定在哪些广播台播出。每个广播台覆盖特定的州，不同广播台的覆盖区域可能重叠。

精确解：列出每个可能的广播台集合（幂集），选出覆盖全 50 个州的最小集合。可能的子集有 2ⁿ 个，运行时间为 O(2ⁿ)，广播台一多就无法在合理时间内计算。

近似算法（贪婪算法）：

  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()

while states_needed:
    best_station = None
    states_covered = set()
    for station, states in stations.items():
        covered = states_needed & states      # 交集
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered
    states_needed -= states_covered
    final_stations.add(best_station)

print final_stations   # set(['ktwo', 'kthree', 'kone', 'kfive'])

集合操作：

>>> fruits = set(["avocado", "tomato", "banana"])
>>> vegetables = set(["beets", "carrots", "tomato"])
>>> fruits | vegetables   # 并集
set(["avocado", "beets", "carrots", "tomato", "banana"])
>>> fruits & vegetables   # 交集
set(["tomato"])
>>> fruits - vegetables   # 差集
set(["avocado", "banana"])

贪婪算法的运行时间为 O(n²)，比 O(2ⁿ) 快得多。

判断近似算法优劣的标准：速度有多快；得到的近似解与最优解的接近程度。

NP完全问题

旅行商问题和集合覆盖问题都属于 NP 完全问题——以难解著称的问题。很多非常聪明的人都认为，根本不可能编写出可快速解决这些问题的算法。

旅行商问题详解：旅行商要前往 n 个城市，找出最短路径。可能的路径数为 n!：

  • 2 个城市：2 条
  • 3 个城市：6 条
  • 4 个城市：24 条
  • 5 个城市：120 条
  • 10 个城市：3 628 800 条

可能的路线数增加得非常快，城市很多时根本无法找出正确解。

如何识别 NP 完全问题：

  • 元素较少时算法的运行速度非常快，但随着元素数量增加，速度会变得非常慢
  • 涉及「所有组合」的问题通常是 NP 完全问题
  • 不能将问题分成小问题，必须考虑各种可能的情况
  • 如果问题涉及序列（如城市序列）且难以解决，可能是 NP 完全问题
  • 如果问题涉及集合（如广播台集合）且难以解决，可能是 NP 完全问题
  • 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是 NP 完全问题

小结

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