内容:
- 如何处理不可能完成的任务;没有快速算法的问题(NP完全问题)
- 学习是被NP完全问题,以免浪费时间去寻找解决他们的快速算法
- 学习近似算法,使用它们可快速中找到NP完全问题的近似解
- 学习贪婪策略——一种非常简单的问题解决策略
8.1教室调度问题
贪婪算法:每步都采取绝不最优解,最终的到的就是全局最优解。
贪婪苏凡并非任何情况下都有效,但它易于实现。
8.2背包问题
贪婪算法并不能得到最优解,但是非常接近。
在有些情况下,完美是优秀的敌人。 有时,只需找到一个单只解决问题的算法啊,此时贪婪算法正好派上用场,其易于实现,得到的结果又与最优结果相当接近。
8.3近似算法
贪婪算法是一种近似算法,在获得精确解需要时间太长时,可使用近似算法。
判断近似算法优劣的标准如下:
- 速度有多快
- 的到的近似解与最优解的接近程度
使用贪婪算法解决广播台覆盖问题。
1 # You pass an array in, and it gets converted to a set. 2 states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) 3 4 stations = {} 5 stations["kone"] = set(["id", "nv", "ut"]) 6 stations["ktwo"] = set(["wa", "id", "mt"]) 7 stations["kthree"] = set(["or", "nv", "ca"]) 8 stations["kfour"] = set(["nv", "ut"]) 9 stations["kfive"] = set(["ca", "az"])10 11 final_stations = set()12 13 for station, states in stations.items():14 # print "states: ", states15 print "station: ", station16 print "\n"17 18 while states_needed:19 best_station = None20 states_covered = set()21 for station, states in stations.items():#station is index, states is element22 covered = states_needed & states # get intersection23 print "covered: ", covered24 print "states_covered: ", states_covered25 print "states: ", states26 print "station: ", station27 print "***********\n"28 29 if len(covered) > len(states_covered):30 best_station = station31 states_covered = covered32 33 states_needed -= states_covered34 final_stations.add(best_station)35 36 print final_stations
说明:
- 代码中的for循环对广播站进行进行遍历,查找出能覆盖最多州的广播站;
- for循环结束后,把已覆盖的州从集合中删除,更新最终解的集合;
- 如果还有未覆盖的州,继续执行步骤1(第二部中,应该把找到的广播 站删除);
- 直到没有需要覆盖的州,则查找结束。
8.4 NP完全问题
- 定义:NP完全问题的简单定义是,以难解著称的问题,如旅行商问题和集合覆盖问题。很多人认为,没有可以快速结果这些问题的算法。
- 如何识别:
- 元素较少时算法的运行速度非常快,但随着元素的增加,速度变得非常慢
- 涉及“所有组合”的问题通常是NP完全问题
- 不能将问题分成小问题,必须考虑各种可能的情况,这可能是NP完全问题
- 如果涉及集合且难以解决,它可能是NP完全问题
- 如果问题涉及集合且难以解决,他可能是NP完全问题
- 如果问题可转换为集合覆盖问题或旅行商问题,它肯定是NP完全问题
8.5小结
- 贪婪算法寻找局部最优解,企图以这种方式获得全局最优解
- 对于NP完全问题,还没有找到快速解决方案
- 面临NP完全问题时,最佳的做法是使用近似算法
- 贪婪算法易于实现、运行速度快,是不错的近似算法
贪心算法C语言实现: