贪婪算法

集合覆盖问题

问题描述

你想要办一个广播节目，需要让每个州的居民都能够看到你的节目，请确定你需要你的节目在那些频道中播出，每个频道的覆盖范围都不同

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'])

上面的代码片段中，key值表示频道的名字，对应的集合内容表示频道所覆盖的州名称

你需要让你的节目覆盖以下州

states_needed = set(['mt','wa','or','id','nv','ut'])

解决步骤

近似算法：

• 选出这样的一个广播台，即它覆盖了最多的未覆盖州，即便这个广播台覆盖了一些已覆盖的州，也没关系
• 重复第一步，直到覆盖了所有的州

判断近似算法的优劣

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

对于这个问题，首先要尽量选择覆盖范围最广的频道，每次的选择都要保证频道的覆盖范围最广

final_stations = set()  #用于保存最后的结果，州名称

while states_needed:    #当需要覆盖的州还不为空，则继续循环
    best_station = None #每一轮遍历，选择最优的州，用于存储
    statas_covered = set()  #已经覆盖的返回

    for station,states_for_station in stations.items(): #对每个频道进行遍历
        covered = states_for_station & states_needed    #找出每个频道的范围和需要范围的交集
        if len(covered) > len(statas_covered):  #找到所有频道中，覆盖范围最广的一个
            best_station = station
            statas_covered = covered
    states_needed -= statas_covered     #求出还剩下那些范围需要覆盖
    final_stations.add(best_station)    #将找到的最优频道放在最后的结果中

print(final_stations)   #打印最终结果

NP完全问题

定义

NP完全问题可以简单的定义成，以难解决著称的问题

它们有一些比较相似的地方，比如，都需要计算所有的解，然后从中选出最小/最短的那个。这两个问题都属于NP完全问题

因此，对于一个NP完全问题来说，最好的方法就是近似求解

如何识别

NP完全问题可以通过下面的简单方法进行判定

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