用贪心法求解的问题应具有的性质?

用贪心法求解的问题应具有的性质？

贪心算法是计算机科学中基础的算法之一。贪心算法采用贪心策略，即在当前情况下选择最优的决策，但往往不能得到全局最优解。因此，贪心算法要求问题具有一些特定的性质，使之能够得到正确而高效的解。

1. 最优子结构

最优子结构是一个问题必须满足的重要条件。它的意义在于，问题的最优解可以通过一系列子问题的最优解计算得出。这就是说，问题可以分解成更小的子问题，每个子问题的最优解组合起来构成了问题的最优解。贪心算法适合解决这样的问题，因为贪心策略可以逐步求解每个子问题的最优解，并将它们合并成整个问题的最优解。例如，哈夫曼编码问题就具有最优子结构。

2. 贪心选择性质

贪心选择性质是指，问题在每个阶段只能选择当前最优的决策，而这些决策加在一起就是问题的最优解。换句话说，当前状态下采取的最优决策不会影响以后的状态。这种选择性质在贪心算法的基础理论中很重要，因为它保证了局部最优解的正确性，从而得到全局最优解。这种特性也必须在问题本身存在，例如活动选择问题中，每个活动都有一个结束时间，问题要求选择最大数量的活动，使得它们的结束时间不重叠。

3. 可行性

一个问题必须是具有可行性的，才能用贪心算法来求解。可行性指的是对于给定实例，存在满足条件的解答，否则贪心算法无法处理问题。例如，钞票找零问题具有可行性，因为无论是人还是机器，只要有一定数量的钞票和零钱，就能找到给定金额的零钱。

4. 子问题的重叠性

子问题的重叠性意味着每个子问题都与其他子问题共享子结构。这种性质常常导致子问题之间存在依赖关系。在贪心算法中，这种重叠性通常要求问题没有严格限制，允许贪心策略在每个阶段选择保证最优的决策。例如，活动选择问题中，每个活动的时间都是固定的，因此贪心算法可以在每个子问题中选择在开始时间最早的活动。

5. 无后效性

无后效性是指在求解过程中，我们不关心之前的状态及其以前所做的决策，只关心当前状态能够得到什么样的全局最优解。这种性质对于贪心算法的恰当性非常重要。在贪心策略中，每一步都需要选择最优的决策，当前的决策不能回头，也不能修改。这种设计决定了当前状态的决策只会影响到以后的状态，而不会影响到之前的状态。

综上所述，贪心算法的实现需要问题具有最优子结构、贪心选择性质、可行性、子问题的重叠性以及无后效性等属性。这些属性保证了贪心算法得以快速求解多种问题，例如甘特图调度，哈夫曼编码，钞票找零等。