欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

python搜索算法实现——(二)贪婪算法

程序员文章站 2022-06-04 10:52:20
...

贪婪算法简介

假设你办了个广播节目,要让全美国50个州的听众都能听得到,为此, 你需要决定在哪些广播台播出。每个广播台台播出都需要费用,所以你需要尽可能地在更少的广播台播出节目。现有广播台名单如下:
python搜索算法实现——(二)贪婪算法
每个广播台都覆盖不同的范围,但是有些是重复的
python搜索算法实现——(二)贪婪算法
如何才能找出覆盖全美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)