..
0x07 贪心
贪心是一种在每次决策时采取当前意义下最优策略的算法，使用贪心法要求问题的整体最优性可以由局部最优性导出。
贪心算法的正确性需要证明，常见手法如下。
- 微扰（邻项交换）
证明在任意局面下，任何对局部最优策略的微小改变都会造成整体结果变差。
经常用于以 “排序” 为贪心策略的证明。 - 范围缩放
证明任何对局部最优策略作用范围的扩展都不会造成整体结果变差。 - 决策包容性
证明在任意局面下，做出局部最优策略以后，在问题状态空间中的可达集合包含了作出其他任何决策后的可达集合。
换言之，这个局部最优策略提供的可能性包含其他所有策略提供的可能性。 - 反证法
- 数学归纳法。