整形网站整站源码,微信咋做自己的网站,有网站和无网站的区别,三明网站建设tudouly数据结构和算法 基于《算法图解》—Aditya Bhargava 和《数据结构》—严蔚敏
第8章 贪婪算法
贪婪算法的优点#xff1a; 简单易行#xff0c;让每一步都选择局部最优解#xff0c;最终得到的就是全局最优解。 贪婪算法是近似算法#xff1a;在获得精确解需要的时间太长时…数据结构和算法 基于《算法图解》—Aditya Bhargava 和《数据结构》—严蔚敏
第8章 贪婪算法
贪婪算法的优点 简单易行让每一步都选择局部最优解最终得到的就是全局最优解。 贪婪算法是近似算法在获得精确解需要的时间太长时可以使用近似算法。
判断近似算法优劣的标准如下 速度有多块。 得到的近似解与最优解的接近程度。
8.1 集合覆盖问题 例如解决经典的集合覆盖问题——选择最优的广播电台 假设办了个广播节目要让全美50个州的听众都收听得到。为此需要决定在哪些广播台播出。在每个广播台播出都需要支付费用因此要尽可能少的广播台播出。
#首先创建一个列表包含要覆盖的州
states_needed set([mt, wa, id, nv, ut, ca, az]) #传入一个数组它被转换为集合。
#创建可供选择的广播台清单使用散列表表示。
station {}
station[kone] set([id,nv,ut])
station[ktwo] set([wa,id,mt])
station[kthree] set([or,nv,ca])
station[kfour] set([nv,ut])
station[kfive] set([ca,az])
#创建一个集合来存储最终选择的广播台。
final_station set()#计算结果
while states_needed:best_staion Nonestates_covered set()for station, states in stations.items():covered states_needed states #计算交集if len(covered) len(states_covered):best_station stationstates_covered coveredstates_needed - states_coveredfinal_stations.add(best_station)
print final_stations8.2 NP完全问题 Non-deterministic Polynomial的问题即多项式复杂程度的非确定性问题。
判断NP完全问题的方法
元素较少时算法的运行速度非常快但随着元素数量的增加速度会变得非常慢。涉及“所有组合”的问题通常是NP完全问题。不能将问题分成小问题必须考虑各种可能的情况。如果问题涉及序列且难以解决(如旅行商问题中的城市序列)。如果问题涉及集合且难以解决(如广播台集合)。如果问题可转换为集合覆盖问题或者旅行商问题就肯定是NP问题。
8.3 小结 贪婪算法寻找局部最优解企图以这种方式来获得全局最优解。 对于NP完全问题还没有找到快速解决方案。 面临NP完全问题时最佳的做法是适用近似算法。 贪婪算法易于实现、运行速度快是不错的近似算法。
——持续修改完善中…
