贪心算法2

使用条件利用贪心法求解的问题应具备如下2个特征[4]。1、贪心选择性质一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解[4]。2、最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析[4]。解题策略贪心算法不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优选择。使用贪心策略要注意局部最优与全局最优的关系，选择当前的局部最优并不一定能推导出问题的全局最优。贪心策略解题需要解决以下两个问题：[5]1、该问题是否适合使用贪心策略求解，也就是该问题是否具有贪心选择性质[5]；2、制定贪心策略，以达到问题的最优解或较优解[5]。要确定一个问题是否适合用贪心算法求解，必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解[5]。存在问题贪心算法也存在如下问题：[6]1、不能保证解是最佳的。因为贪心算法总是从局部出发，并没从整体考虑[6]；2、贪心算法一般用来解决求最大或最小解[6]；3、贪心算法只能确定某些问题的可行性范围[6]。