贪婪算法

本文参考书籍《图解算法》

一、在了解贪婪算法之前，首先需要了解一下 NP完全问题

NP完全问题(NP-C问题)，是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。。。。。。。

具体的详细描述可以参考百度百科，不过其中解释实在晦涩难懂，下面就讲一下一个经典的NP完全问题–旅行商问题

有一位旅行商。 他需要前往5个城市。
这位旅行商(姑且称之为Opus吧)要前往这5个城市，同时要确保旅程最短。为此，可考虑 前往这些城市的各种可能顺序。

对于每种顺序，他都计算总旅程，再挑选出旅程最短的路线。5个城市有120种不同的排列方式。因此，在涉及5个城市时，解决这个问题需要执行120次操作。涉及6个城市时，需要执行720 次操作(有720种不同的排列方式)。涉及7个城市时，需要执行5040次操作!
推而广之，涉及n个城市时，需要执行n!(n的阶乘)次操作才能计算出结果。因此运行时间 为O(n!)，即阶乘时间。除非涉及的城市数很少，否则需要执行非常多的操作。如果涉及的城市 数超过100，根本就不能在合理的时间内计算出结果——等你计算出结果，太阳都没了。

上面的问题就是一个典型的NP完全问题，随着城市数量的增加，需要计算的路线数量会急剧增加。为了节约时间，因此我们需要找到一种简单的方法进行计算。其中一种方法就是近似算法。而我们的主题贪婪算法就是一种近似算法。

二、下面再举一个集合覆盖问题，来详细讲解一下贪婪算法

假设你办了个广播节目，要让全美50个州的听众都收听得到。为 此，你需要决定在哪些广播台播出。在每个广播台播出都需要支付费 用，因此你力图在尽可能少的广播台播出。现有广播台名单如下。

每个广播台都覆盖特定的区域，不同广播台的覆盖区域可能重叠。

如何找出覆盖全美50个州的最小广播台集合呢?听起来很容易，但其实非常难。具体方法如下。
(1) 列出每个可能的广播台集合，这被称为幂集(power set)。可能的子集有2n个。
(2) 在这些集合中，选出覆盖全美50个州的最小集合。
问题是计算每个可能的广播台子集需要很长时间。由于可能的集合有2n个，因此运行时间为 O(2n)。如果广播台不多，只有5~10个，这是可行的。但如果广播台很多，结果将如何呢?随着 广播台的增多，需要的时间将激增。

近似算法
贪婪算法可化解危机!使用下面的贪婪算法可得到非常接近的解。
(1) 选出这样一个广播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖 的州，也没有关系。
(2) 重复第一步，直到覆盖了所有的州。
这是一种近似算法(approximation algorithm)。在获得精确解需要的时间太长时，可使用近
似算法。判断近似算法优劣的标准如下:  速度有多快;
 得到的近似解与最优解的接近程度。 贪婪算法是不错的选择，它们不仅简单，而且通常运行速度很快。在这个例子中，贪婪算法
的运行时间为O(n2)，其中n为广播台数量。 下面来看看解决这个问题的代码。

states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])   # 需要覆盖的州
final_stations = []
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"])

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                                      # 则将该station设置为best
            states_covered = covered                                    # 遍历所有的电台，取出匹配值最大的电台作为最佳电台
    states_needed -= states_covered                                     # 减去已匹配电台
    final_stations.add(best_station)                                    # 将此电台天加到需求结果

此种算法相对简单，遍历所有的电台，找出与所需求州匹配最多的电台，然后除去已匹配的电台，继续循环，遍历所有的电台，直到全部匹配所有的州。

时间比照

由此可见，贪婪算法会大大缩短计算时间

三、贪婪算法弊端
毫无疑问，贪婪算法的弊端显而易见，就是与正确答案之间存在误差，所以贪婪算法的使用有局限性，比如说，此份计算是为了进行科学实验，一丝一毫都不能出错，那显然不能使用贪婪算法。