贪心算法理论基础
# 1. 什么是贪心算法
⭐ 贪心算法总是做出在当前看来是最优的选择,也就是说,贪心算法并不从整体最优上考虑,所作的选择只是局部最优选择。
虽然贪心算法不是对所有问题都能得到整体最优解,但对很多问题都能产生整体最优解,或者最优解的很好的近似解。

# 2. 贪心算法的基本要素
动态规划问题的两个基本性质:
- 最优子结构
- 子问题重叠性质
而贪心算法的两个基本性质:
最优子结构
贪心选择性质
贪心选择性质是指:所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到
# 3. 贪心算法和动态规划算法
💡 贪心选择性质是贪心算法与动态规划算法的主要区别:
- 在动态规划算法中,每步所做的选择依赖于相关子问题的解,所以只有解决相关子问题后,才能做出选择。
- 而在贪心算法中,仅在当前状态下做出最好选择,即局部最优选择,再去解做出这个选择后产生的相应的子问题。也就是说,贪心算法所做的贪心选择可以依赖过去所做过的选择,但绝不依赖将来所作的选择,也不依赖子问题的解。
⭐ 正是由于这种差别,动态规划算法是自底向上
的,而贪心算法是自顶向下
的,以迭代的方式做出相继的贪心选择,每做一次贪心选择,就将所求问题简化为规模更小的子问题。
# 4. 贪心策略在图算法中的应用
几个重要的图算法基本都使用了贪心策略,详细可见【图】相关章节
单源最短路径:
Dijkstra 算法
最小生成树:
Prim 算法
Kruskal 算法
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10