贪婪算法
贪婪算法的优点——简单易行！贪婪算法很简单：每步都采取最优的做法。用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。
集合覆盖问题
假设你办了个广播节目，要让全美50个州的听众都收听得到。你需要决定在哪些广播台播出。力图在尽可能少的广播台播出。每个广播台都覆盖特定的区域，不同广播台的覆盖区域可能重叠。
如何找出覆盖全美50个州的最小广播台集合呢？具体方法如下：
- 列出每个可能的广播台集合，这被称为幂集（power set）。可能的子集有2 n 个。
- 在这些集合中，选出覆盖全美50个州的最小集合。
贪婪算法可化解危机！使用下面的贪婪算法可得到非常接近的解。
- 选出这样一个广播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖的州，也没有关系。
- 重复第一步，直到覆盖了所有的州。
这是一种近似算法（approximation algorithm）。在获得精确解需要的时间太长时，可使用近似算法。判断近似算法优劣的标准如下：
- 速度有多快；
- 得到的近似解与最优解的接近程度。
贪婪算法是不错的选择，它们不仅简单，而且通常运行速度很快。在这个例子中，贪婪算法的运行时间为 O ( n 2 )，其中 n 为广播台数量。
示例代码：
#传入一个数组，他被转换为集合 states_needed = set(["mt","wa","or","id","nv", "ut","ca", "az"]) #可供选择的广播台清单，用散列表 #键为广播台的名称，值为广播台覆盖的州 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"]) #储存最终选择的广播台 final_stations = set() #循环，直到states_needed为空 while states_needed: #选择覆盖了最多的未覆盖州的广播台 best_station = None states_covered = set() for station,states_for_station in stations.items(): #计算交集 covered = states_needed & states_for_station if len(covered) > len(states_covered): best_station = station states_covered = covered states_needed -= states_covered final_stations.add(best_station) print(final_stations)
NP 完全问题
NP(Non-Deterministic Polynomial, 非确定多项式)问题。
P问题：一个问题可以在多项式（O(n^k)）的时间复杂度内解决。
NP问题：一个问题的解可以在多项式的时间内被验证。
NP-hard问题：任意np问题都可以在多项式时间内归约为该问题，但该问题本身不一定是NP问题。归约的意思是为了解决问题A，先将问题A归约为另一个问题B，解决问题B同时也间接解决了问题A。
NPC问题：既是NP问题，也是NP-hard问题。
判断NP完全问题
1.元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
2.涉及“所有组合”。
3.不能将问题分成小问题，必须考虑各种可能的情况。
4.如果问题涉及序列（如旅行商问题中的城市序列）且难以解决。
5.如果问题涉及集合（如广播台集合）且难以解决。
6.如果问题可转换为集合覆盖问题或旅行商问题。
小结
- 贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。
- 对于NP完全问题，还没有找到快速解决方案。
- 面临NP完全问题时，最佳的做法是使用近似算法。
- 贪婪算法易于实现、运行速度快，是不错的近似算法。
小贴士
集合，集合类似于列表，只是同样的元素只能出现一次，即集合不能包含重复的元素.
>>>arr = [1, 2, 2, 3, 3, 3]
并且你将其转换为集合。
>>> set(arr)
set([1, 2, 3])
>>> fruits | vegetables 并集
>>>fruits & vegetables 交集
分类就是编组。
回归就是预测结果（如一个数字）。
映射函数
>>> arr1 = [1, 2, 3, 4, 5]
>>> arr2 = map(lambda x: 2 * x, arr1)
[2, 4, 6, 8, 10]
- 还没有人评论，欢迎说说您的想法！
客服
