6.3 贪心算法

文档摘要

6.3 贪心算法 6.3 贪心算法贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。换句话说，算法在解决问题的过程中，总是做出在当前看来是最好的选择，而不从整体最优的角度加以考虑。贪心算法并非对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解或者是整体最优解的近似解。因此，贪心算法是一种常用的算法设计范式。 6.3.1 贪心算法的核心思想贪心算法的核心思想可以概括为以下几点：局部最优选择：在算法的每一步，都做出当前状态下最优的选择。无后效性：一旦做出选择，就不能改变，后续的选择不会影响之前的选择。逐步构造：通过一系列局部最优选择，逐步构造出问题的解。