【有书共读】《算法图解》第八章读书笔记——贪婪算法

• 假设你办了个广播节目，要让全美50个州的听众都收听得到。为此，你需要决定在哪些广播台播出。在每个广播台播出都需要支付费用，因此你力图在尽可能少的广播台播出。每个广播台都覆盖特定的区域，不同广播台的覆盖区域可能重叠。

具体方法如下：

①列出每个可能的广播台集合，这被称为幂集（power set）。可能的子集有2**n个。

②在这些集合中，选出覆盖全美50个州的最小集合。

由于可能的子集有2**n个，因此运行时间为O(2**n)。

用贪婪算法可得到非常接近的解：

①选出这样一个广播台，它覆盖了最多的未覆盖的州。即使有重复的州也没有关系

②重复第一步，直到覆盖了所有的州

这是一种近似算法。判断近似算法优劣的标准如下：

①速度有多快

②得到的近似解与最优解的接近程度。在这个例子中贪婪算法的运行时间为O（n**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()

②计算答案

需要从中选择覆盖了最多的未覆盖州的广播台。将整个广播台存储在best_station 中。

states_needed = (["mt", "wa", "or", "id", "nv", "ut","ca", "az"])　　　　#这个代码有问题没解决
stations = {}
stations["kone"] = (["id", "nv", "ut"])
stations["ktwo"] = (["wa", "id", "mt"])
stations["kthree"] = (["or", "nv", "ca"])
stations["kfour"] = (["nv", "ut"])
stations["kfive"] = (["ca", "az"])
final_stations = ()
while states_needed:
    best_station = ()
    states_covered = ()
    for station, states_for_station in stations.items():
        covered = states_needed and states_for_station
        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'])

states_covered 是一个集合，包含该广播台覆盖的所有未覆盖的州。 for 循环迭代每个广播台，并确定它是否是最佳的广播台。下面来看看这个 for 循环的循环体。

covered 是一个集合，包含同时出现在 states_needed 和states_for_station 中的州；

贪婪算法和精确算法的运行时间对比：