python搜索算法实现——（二）贪婪算法

贪婪算法简介

假设你办了个广播节目，要让全美国50个州的听众都能听得到，为此， 你需要决定在哪些广播台播出。每个广播台台播出都需要费用，所以你需要尽可能地在更少的广播台播出节目。现有广播台名单如下：

每个广播台都覆盖不同的范围，但是有些是重复的

如何才能找出覆盖全美50个州的最小广播台集和呢?先提供一种方法：
（1）列出每种可能的广播台集和，称之为幂集，总共有2^n种集和
（2）找出这2^n种集和中覆盖全美50个州的最小集合。
以上算法的问题是计算所有集和的时间需要很多，假如有100个广播台，那么集和一共2^100次方，这可是一个非常大的数！
那么，有没有一种算法可以快速的解决这种类似的问题呢？有，就是贪婪算法。
贪婪算法是近似算法的一种，它的解决方法如下：
（1）选出一个广播台，这个广播台覆盖了最多的未覆盖州，即便这个广播台覆盖了一些已经覆盖的州也没有关系。
（2）重复第一步，直到覆盖了所有的州
只要简单的两步！而且贪婪算法的时间复杂度为O(n^2)，其中n为广播台数量，在n比较大的时候远比第一种方法速度快。

但是贪婪算法并不一定能得到最优解，它获取的只是近似的最优解。很多时候，对于难以计算的问题，才会使用贪婪算法，快速的得到近似解。衡量贪婪算法有两点：
（1）速度有多快
（2）得到的近似解与最优解的接近程度

最后，总结一下贪婪算法的实现步骤：
（1）找到局部最优解
（2）到一个新的局部，重复上一步

代码实现：

"""
假设你办了个广播节目，要让全美50个州的听众都收听得到，为此，
你需要决定在哪些广播台播出，出于预算，你要力图在尽可能少的
广播台播出，现在广播台名单和其覆盖位置如下：
{'KONE': ID,NV,UT}{'KTWO': WA,ID,MT},{KTHREE : OR,NV,CA}
{KFOUR : NV,UT},{KFIVE : CA, AZ}
"""
# 要覆盖的州
states_needed = set(['mt', 'wa', 'or', 'id', 'nv', 'ut', 'ca', 'az'])

# 广播台清单
stations = dict()
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_for_station in stations.items(): 
        # 计算需要覆盖的州和每个广播台覆盖的州的交集 
        covered = states_needed & 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)