1 处理不可能完成的人物
2 识别np完全问题
3 近似算法 快速找到NP问题的近似解
4 贪婪策略
近似算法实现
1 使用一个集合 states_needed记录所有要覆盖的州(使用集合的原因是集合不能包含重复的元素)
2 一个可供选择的电台名单 用散列表表示 station={}
3 使用一个集合存储最终选择的电视台 fina_station=set()
4 best_station用于存储被选中的电台
算法实现
NP完全问题
简单定义 根本不可能编写出可快速解决这些问题的算法
1元素少的时候运行速度非常快,但随着元素增加,速度会变得非常慢
2 设计"所有组合"的问题通常是NP完全问题
3 不可能分解成小问题 必须考虑各种可能的情况 这可能是NP完全问题
4 如果问题涉及序列 且难以解决可能是NP完全问题
5 问题涉及集合且难以解决
6 如果问题可转换为集合覆盖问题或旅行商问题那么他肯定是NP完全问题
