《算法图解》总结第 8 章：贪婪算法

2023-10-30

仅用于记录学习，欢迎批评指正，大神勿喷

系列文章目录

文章目录

系列文章目录
贪婪算法
NP完全问题
- 定义
- 如何识别NP完全问题

贪婪算法

贪婪算法很简单：每步都采取最优的做法，用专业术语来说，就是每步都选择局部最优解，最终得到的就是全局最优解。（贪婪算法并非在任何情况下都行之有效，第7章乐谱换架子鼓就是一个典型例子。）
贪婪算法有时不能获得最优解，但是非常接近，有时你只需找到一个能够大致解决问题的算法，此时就可使用贪婪算法，这是一种近似算法。近似算法判断优劣的标准：
（1）速度有多快；
（2）得到的近似解与最优解的接近程度；
贪婪算法优点：易于实现，运行速度快，是不错的近似算法。

补充知识

并集、交集、差集
和数学中学的一样，这里作补充的是实现代码（Python），直接借用例子进行说明。
案例：

fruits = set(["avocado","tomato","banana"])
vegetables = set(["beets","carrots","tomato"])

并集：将集合合并

fruits | vegetables

输出结果：

{'avocado', 'banana', 'beets', 'carrots', 'tomato'}

交集：找出两个集合中都有的元素

fruits & vegetables

输出结果：

{'tomato'}

差集：从一个集合中剔除出现在另一个集合中的元素

fruits - vegetables

输出结果：

{'avocado', 'banana'}

应用案例：集合覆盖问题

案例：假设办个广播节目，要让全美50个州的听众都收听到，为支付较低的费用，尽量选择尽可能少的广播台播出。以下图为例，每个广播台能覆盖的特定区域，不同广播台的覆盖区域可能重叠。
在这里插入图片描述
将上图整理成表，显示如下：

案例分析

第一步：创建一个列表,包含要覆盖的州，要用集合来表示，集合类似于列表，但是集合中不能包含重复的元素

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()

第四步：贪婪算法实现

# 只要州还没覆盖完，一直执行while循环
while states_needed:
    # 定义最初最好的广播台
    best_station = None
    # 定义一个集合，存储已经覆盖的州
    states_covered = set()
    ''' 
    for循环迭代每个广播台，并确定它是否是最佳，items()存储键值(广播台和相应的覆盖州)
    即每次仅能确定一个最佳的广播台
    '''
    for station,states_from_station in stations.items():
        # 需要覆盖的州和当前该广播台能覆盖的州的交集
        covered = states_needed & states_from_station 
        # 如果当前广播台州交集的个数大于当前要覆盖的州
        if len(covered) > len(states_covered):
            # 就替换为最佳的广播台
            best_station = station
            # 替换已经覆盖的州
            states_covered = covered
    # for循环结束一次后，要从需要覆盖的州中减去已经覆盖过的州
    states_needed -= states_covered 
    # 打印剩余需要覆盖的州
    print('states_needed:',states_needed)
    '''
    添加最佳的广播台，并开始下一轮新的while循环直至需要覆盖的州为空 
    （注：新一轮while循环中的best_station和states_covered不是for循环后的，还是while循环中最初定义
    的那些，因为for循环只是while循环中的一块，这个必须想明白）
    '''  
    final_stations.add(best_station)   
print(final_stations)

输出结果：

F:\anaconda\python.exe E:/lecode/tanlan.py  # 代码存储位置，方便自己下次找到  
states_needed: {'or', 'az', 'ca', 'wa', 'mt'}
states_needed: {'or', 'az', 'ca'}
states_needed: {'az'}
states_needed: set()
{'ktwo', 'kone', 'kthree', 'kfive'}

NP完全问题

定义

NP完全问题的简单定义是以难解著称的问题，如集合覆盖问题和旅行商问题，这两个问题的共同之处在于我们需要计算所有的解，并从中选择最小或者最短的那个，感兴趣的同学可以去了解一下旅行商问题。这是一类很多聪明人都认为，根本不可能编写出可快速解决这些问题的算法。

如何识别NP完全问题

我们为什么会关注到NP完全问题的识别这个问题呢？若我们能识别出一个问题是NP完全问题，那么我们就可以用近似求解的方法去解决这个问题，而不用再去费力去求解完美解了。尽管我们没有办法判断某个问题是不是NP完全问题，但是还是有一些蛛丝马迹可引导我们做出判断：
（1）元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢；
（2）涉及“所有组合”的问题通常是NP完全问题；
（3）不能将问题分成小问题，必须考虑各种可能的情况，这可能是NP完全问题；
（4）如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题；
（5）如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题；
（6）如果问题可转换为集合覆盖问题或旅行商问题，那它肯定就是NP完全问题。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)