6.贪心算法
贪心
贪心是一种在每一次决策时都采用当前意义下最优策略的算法，因此，使用贪心算法要求问题的整体最优性可以由局部最优性导出。
贪心算法的正确性需要证明，常见的证明手段有：
- 微扰（邻项交换） 证明在任意局面下，任何对局部最优策略的微小改变都会造成整体结果变差，经常用于以排序为贪心策略的证明。
- 范围缩放 证明任何对局部最优策略作用范围的扩展都不会造成整体结果变差。
- 决策包容性
证明在任意局面下，做出局部最优策略以后，在问题状态空间中的可达到集合包含了做出其他任何决策之后的可到达集合。换言之，这个局部最优解提供的可能性包含其他所有策略提供的可能性。 - 反证法
- 数学归纳法
------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
微信打赏