贪婪算法回顾
回顾
还记的贪婪算法么? 如果你不记得了, 看了下面这个例子你一定会想起来, 因为这个例子太普遍了, 几乎每个将贪婪算法的地方, 第一个例子都是它, 言归正传.
问题: 现在有如下课程表, 要将这些课尽可能多的安排在教室A内.
| 课程名 | 开始时间 | 结束时间 |
|---|---|---|
| 语文课 | 9:00 | 10:00 |
| 数学课 | 9:30 | 10:30 |
| 音乐课 | 10:00 | 11:00 |
| 政治课 | 10:30 | 11:30 |
| 美术课 | 11:00 | 12:00 |
首先将所有课程都安排在教师A是不现实的, 因为时间上存在冲突. 那改怎么安排呢?
这个问题很难, 对吧. 算了, 至少我第一次看的时候, 完全没有头绪. 但看了下面的思路, 你又会发现, 啊?这么简单么?
具体思路
-
选出结束时间最早的课程, 将它加到教室A的第一节课
-
找出在当前教室A最后一节课的结束时间之后开始, 并且结束时间最早的课程, 将其加到教室A的课表中
-
重复步骤2
经过上面的步骤, 得出的课表为:
| 课程名 | 开始时间 | 结束时间 |
|---|---|---|
| 语文课 | 9:00 | 10:00 |
| 音乐课 | 10:00 | 11:00 |
| 美术课 | 11:00 | 12:00 |
如何, 是不是感觉这个算法太简单了, 简单到我都不敢相信最终的结果是正确的.
但是这正是贪婪算法的优点, 简单, 容易实施.
贪婪算法的思想就是(个人理解), 每一步都找到当前状态的最优解, 继续.
显然,贪婪算法并不总是能够找到最优解
来了, 又来了, 又是一个被用烂了的例子, 但我就是要用, 哼.
问题: 现在有一个小偷, 带着一个可以装35kg重东西的包包, 他要将最贵重的东西带走, 那么, 贪婪算法思路如下:
-
将可装下的最贵的东西装入背包
-
重复步骤1
但是, 如果物品如下:
-
物品A: 价值300, 重量30kg
-
物品B: 价值200, 重量20kg
-
物品C: 价值150, 重量15kg
按照上面的思路, 装入的内容为: 物品A, 总价值300
但是, 很显然, 如果装入的是: 物品B+物品C, 总价值350
这时, 贪婪算法找出的就不是最优解了.
如果换一种思路呢?
-
将可装下的最轻的东西装入背包
-
重复步骤2
你很惊喜的发现, 结果就是我们要的, 但是, 不好意思, 这只是这种情况下的满足.
如果换一种情况呢? 如果物品A价值是500, 其它条件不变呢?
很显然, 在这里, 物品有价值和重量两个值需要考量, 并不能够单单拿出一个来进行判断(之前的教室问题只需要考虑时间), 需要综合考虑.
其实我个人觉得, 这个例子举得并不恰当, 这种问题本就不适合使用贪婪算法来进行求解. 但是到处都用这个例子, 那我就用吧, 因为我也想不出更好的例子了…….
最终的结果虽然不是最优解, 但是也比较接近了. 主要是算法简单啊
总结
贪婪算法是不是感觉优点动态规划的意思? 没错, 贪婪算法可以说是动态规划的一种特例,也就是说, 所有使用贪婪算法能够解决的问题都可以通过动态规划来解决, 但是反过来并不成立.
其实, 贪婪算法个人感觉并不能叫做贪婪算法, 应该叫贪婪思想, 嘿嘿. 因为它并不是一个具体的算法, 而是一种解决问题的思路:
每一步都寻找当前状态的最有解(局部最优解), 最终得到的就是由所有局部最优解组成的全局最优解, 或接近全局最优解的解
有点只顾眼前利益, 不看长远利益的感觉哈. 这种思路听起来, 简单、容易实现, 甚至简单到让人怀疑他的正确性, 你的怀疑是对的, 并不是每次局部最优解的组合就是全局最优解, 但他的优点就是简单啊, 而且对于上面第一个例子中这样的方法就很好的解决了.
最后, 贪婪算法, 重点在于一个贪字, 哈哈, 请记住贪婪算法的精髓就是贪