算法-贪婪算法简朴介绍
下面是贪婪算法视频课的导学内容.1. 什么是贪婪算法?
简朴来说, 我们称以局部最优进而使得全局最优的一种思想实现出来的算法为贪婪算法.
其过程, 每每分为:
[*]把办理问题分为若干部分
[*]办理每一步的时候, 都选择当前看起来"最优"的选择
[*]“希望” 得到全局最优解
下面来解释两个引号词
“最优”: 上面说的意思是当前看来最优, 而不是从团体的角度看起来最优
“希望”: 意思是按这种思想行止理题目, 有大概会导致最后效果不是最优, 有大概从全局来看是最优效果的意思
2. 贪婪算法简朴的三个例子:
1. 找零问题
情景: 现在你有50块钱, 买了4块钱的东西, 卖家想要用最少的张数找你零钱.
https://i-blog.csdnimg.cn/direct/d7a16f451ea5477ea6b8bcfa153f1f2e.png
此时可以试试贪婪算法.
应该找你的钱数:
50 - 4 = 46
按照贪婪策略, 此时应该找你一张最大面额的, 因此是给你一张20的
46 - 20 = 26 此时还需要找你26元
按照贪婪策略, 此时应该找你一张最大面额的, 因此是给你一张20的
26 - 20 = 6 此时还需要找你6元
按照贪婪策略, 此时应该找你一张最大面额的, 因此是给你一张5元的
6 - 5 = 1 此时还需要找你1元
按照贪婪策略, 此时应该找你一张最大面额的, 因此是给你一张1元的
1 - 1 = 0 此时还需要找你0元
此时找钱竣事
其过程如下:
https://i-blog.csdnimg.cn/direct/0b4556ee2d904a3da321cccb2ccea709.png
2. 最小路径和问题
起点在(0, 0)位置, 规定只能左右上下移动, 在这此中会途经许多方块. 每次途经方块必要加上对应的"路径值", 问怎样才能到达目的地同时求和为最小?
按照贪婪思想, 过程如下:
https://i-blog.csdnimg.cn/direct/d72f90104cfd409c84456fae5458f692.png
3. 背包问题
最大背包容量为: 8单位, 怎样放一些物品, 使得该背包拿到的总价值最高?
https://i-blog.csdnimg.cn/direct/5043777492b94e7cbfd59fe2c30ec84b.png
假设我们按照V去贪婪: ③ * 8 -> 总价值是: 1 * 8 = 8
假设我们按照W去贪婪: ① * 1 + ③ * 3 -> 总价值是: 10 + 1 * 3 = 13
假设我们按照W/V去贪婪: ① * 1 + ③ * 3 -> 总价值是: 10 + 1 * 3 = 13
3. 贪婪算法的特点
[*] 贪婪算法没有标准和模板, 贪婪算法只是一种思想
[*] 贪婪算法必要证明其对错, 对的必要其证明他是对的, 错的必要证明, 或者举反例
对于证明这块来说,
2-1 显然找零问题是对的, 证明如下:
https://i-blog.csdnimg.cn/direct/95e55bd02a62424cab24d7af6972ab47.png
2-2 最小路径和问题 和 背包问题都是错误的, 证明如下(举反例):
https://i-blog.csdnimg.cn/direct/0f0bbbbf6b0949eba577c9cc42a4f18b.png
4. 贪婪算法学习的方式?
[*]碰到不会的很正常, 看多相识析就"大概"会了.
[*]注重证明. 好比"背包"和"路径和"问题贪婪出来都不是最优解.
EOF.
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]