【算法】贪婪算法

贪婪算法

• 每步都采取最优的做法，即每步都选择局部最优解，最终得到的就是全局最优解。
• 在有些情况下，贪婪策略显然不能获得最优解，但非常接近。完美是优秀的敌人，有时候，只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。

近似算法（approximation algorithm）

在获得精确解需要的时间太长时，可使用近似算法。

判断近似算法优劣的标准：

• 速度有多快；
• 得到的近似解与最优解的接近程度。

示例

有一个广播节目，要让全美50个州的听众都收听得到。为此，需要决定在哪些广播台播出。在每个广播台播出都需要支付费用，因此力图在尽可能少的广播台播出

贪婪算法

(1) 列出每个可能的广播台集合，这被称为幂集（power set）。可能的子集有2ⁿ个。

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

近似算法

(1) 选出这样一个广播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖

的州，也没有关系。

(2) 重复第一步，直到覆盖了所有的州。

运行时间为O(n²)，其中n为广播台数量

代码

#创建一个包含要覆盖州的集合
states_needed = set(["mt", "wa", "or", "id", "nv", "ut","ca", "az"])

#创建一个包含所有电台及其覆盖州的散列表
stations={'kone': {'id', 'ut', 'nv'}, 'ktwo': {'wa', 'mt', 'id'}, 'kthree': {'or', 'ca','nv'}, 'kfour': {'ut', 'nv'}, 'kfive': {'az', 'ca'}}

#创建一个集合存储最终选择的广播台
final_stations=set()


while states_needed:
    best_station = None #存储覆盖了最多的未覆盖州的广播台
    states_covered = set()  #包含该广播台覆盖的所有未覆盖的州。
    for station, states in stations.items():    #for循环迭代每个广播台，并确定它是否是最佳的广播台
        covered = states_needed & states   #包含同时出现在states_needed和states_for_station中的州
        if len(covered) > len(states_covered):  #如果该电台覆盖的州是否比best_station多
            best_station = station   #将best_station设置为当前广播台
            states_covered = covered
            
    states_needed -= states_covered   #由于该广播台覆盖了一些州，因此不用再覆盖这些州。
    final_stations.add(best_station)

print(final_stations)

NP完全问题

定义

以难解著称的问题。如旅行商问题和集合覆盖问题。

需要计算所有的解，并从中选出最小/最短的那个

NP完全问题，使用近似算法即可，无需求最优解

如何识别 NP 完全问题

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

小结

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