贪婪算法回顾：精髓就是贪

记的贪婪算法么? 如果你不记得了, 看了下面这个例子你一定会想起来, 因为这个例子太普遍了, 几乎每个将贪婪算法的地方, 第一个例子都是它, 言归正传.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

问题: 现在有如下课程表, 要将这些课尽可能多的安排在教室A内.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

首先将所有课程都安排在教师A是不现实的, 因为时间上存在冲突. 那改怎么安排呢?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

这个问题很难, 对吧. 算了, 至少我第一次看的时候, 完全没有头绪. 但看了下面的思路, 你又会发现, 啊?这么简单么?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

具体思路文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

1. 选出结束时间最早的课程, 将它加到教室A的第一节课
2. 找出在当前教室A最后一节课的结束时间之后开始, 并且结束时间最早的课程, 将其加到教室A的课表中
3. 重复步骤2

经过上面的步骤, 得出的课表为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

如何, 是不是感觉这个算法太简单了, 简单到我都不敢相信最终的结果是正确的.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

但是这正是贪婪算法的优点, 简单, 容易实施.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

贪婪算法的思想就是(个人理解), 每一步都找到当前状态的最优解, 继续.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

显然,贪婪算法并不总是能够找到最优解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

来了, 又来了, 又是一个被用烂了的例子, 但我就是要用, 哼.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

问题: 现在有一个小偷, 带着一个可以装35kg重东西的包包, 他要将最贵重的东西带走, 那么, 贪婪算法思路如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

1. 将可装下的最贵的东西装入背包
2. 重复步骤1

但是, 如果物品如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

1. 物品A: 价值300, 重量30kg
2. 物品B: 价值200, 重量20kg
3. 物品C: 价值150, 重量15kg

按照上面的思路, 装入的内容为: 物品A, 总价值300文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

但是, 很显然, 如果装入的是: 物品B+物品C, 总价值350文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

这时, 贪婪算法找出的就不是最优解了.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

如果换一种思路呢?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

1. 将可装下的最轻的东西装入背包
2. 重复步骤2

你很惊喜的发现, 结果就是我们要的, 但是, 不好意思, 这只是这种情况下的满足.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

如果换一种情况呢? 如果物品A价值是500, 其它条件不变呢?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

很显然, 在这里, 物品有价值和重量两个值需要考量, 并不能够单单拿出一个来进行判断(之前的教室问题只需要考虑时间), 需要综合考虑.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

其实我个人觉得, 这个例子举得并不恰当, 这种问题本就不适合使用贪婪算法来进行求解. 但是到处都用这个例子, 那我就用吧, 因为我也想不出更好的例子了.......文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

最终的结果虽然不是最优解, 但是也比较接近了. 主要是算法简单啊文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

总结文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

贪婪算法是不是感觉优点动态规划的意思? 没错, 贪婪算法可以说是动态规划的一种特例,也就是说, 所有使用贪婪算法能够解决的问题都可以通过动态规划来解决, 但是反过来并不成立.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

其实, 贪婪算法个人感觉并不能叫做贪婪算法, 应该叫贪婪思想, 嘿嘿. 因为它并不是一个具体的算法, 而是一种解决问题的思路:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

每一步都寻找当前状态的最有解(局部最优解), 最终得到的就是由所有局部最优解组成的全局最优解, 或接近全局最优解的解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

有点只顾眼前利益, 不看长远利益的感觉哈. 这种思路听起来, 简单、容易实现, 甚至简单到让人怀疑他的正确性, 你的怀疑是对的, 并不是每次局部最优解的组合就是全局最优解, 但他的优点就是简单啊, 而且对于上面第一个例子中这样的方法就很好的解决了.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html

最后, 贪婪算法, 重点在于一个贪字, 哈哈, 请记住贪婪算法的精髓就是贪文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13200.html