贪婪算法

应用场景

教室课程调度问题，如何让一个教室不冲突地上更多的课？
如何用一个容量有限的背包装价值总和最多的东西？
广播节目费用，如何用最少的费用将广告传播到更广阔的区域？

贪婪算法很简单：每步都采取最优的做法。在这个示例中，你每次都选择结束最早的课。用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。显然，贪婪算法并非在任何情况下都行之有效，但它易于实现！

在有些情况下，完美是优秀的敌人。有时候，你只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。

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

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

NP完全问题

NP完全问题的简单定义是，以难解著称的问题，如旅行商问题和集合覆盖问题。很多非常聪明的人都认为，根本不可能编写出可快速解决这些问题的算法。这种情况下最好就是用简单的近似算法，得到一个近似的答案即可。

如何判断是不是NP完全问题：

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

Python实现代码：

利用最少的广播站台，覆盖所有的目标州：

# You pass an array in, and it gets converted to a set.
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])
#传入一个数组，被转换为集合，集合中的元素不能重复；
#这些是你需要覆盖的州；

stations = {}#用散列表来表示可供选择的广播台清单
stations["kone"] = set(["id", "nv", "ut"])#名叫kone的广播台，可以向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()#使用一个集合来存储最终选择的广播台；

#你不断地循环，直到states_needed为空。
while states_needed:
  best_station = None#存储了覆盖了最多的未覆盖州的广播台；
  states_covered = set()#包含该广播台覆盖的所有未覆盖州；
  for station, states in stations.items():
  #for循环迭代每个广播台，并确定它是否是最佳的广播台。
    covered = states_needed & states
    #计算交集；
    #covered包含了同时出现在states_needed和states_for_station中的州。
    
    #检查该广播台覆盖的州是否比best_station多；
    #如果是这样的，就将best_station设置为当前广播台。
    #最后，你在for循环结束后将 best_station添加到最终的广播台列表中。
    if len(covered) > len(states_covered):
      best_station = station
      states_covered = covered
  states_needed -= states_covered
  #你还需更新states_needed。
 #由于该广播台覆盖了一些州，因此不用再覆盖这些州。
 #states_needed这个列表变短；
  
  final_stations.add(best_station)
  

print (final_stations)

输出：
{'kfive', 'kone', 'kthree', 'ktwo'}

PreviousK最近邻算法 Next动态规划算法

Last updated 5 years ago