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