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

算法图解》总结第 8 章：贪婪算法"/>

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

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

系列文章目录

《算法图解》总结第 1 章：二分查找、大O表示法；
《算法图解》总结第 2 章：数组和链表，选择排序；
《算法图解》总结第 3 章：while循环、递归、栈；
《算法图解》总结第 4 章：分而治之、快速排序；
《算法图解》总结第 5 章：散列表；
《算法图解》总结第 6 章：广度优先搜索；
《算法图解》总结第 7 章：狄克斯特拉算法；
《算法图解》总结第 8 章：贪婪算法
《算法图解》总结第 9 章：动态规划
《算法图解》总结第 10 章：K最近邻算法
《算法图解》总结第 11 章：十种算法简介

文章目录

• 系列文章目录
• 贪婪算法
• • 补充知识
  • 应用案例：集合覆盖问题
  • 案例分析
• 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完全问题。