贪婪算法

集合覆盖问题

问题描述

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

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完全问题
© 版权声明
THE END
喜欢就支持以下吧
点赞0
分享
评论 抢沙发
四曲的头像-四曲博客

昵称

取消
昵称表情代码图片