贪心算法特性
发布网友
发布时间：2024-07-07 08:54
共1个回答
热心网友
时间：2024-07-10 08:02
贪心算法，一种常用的求解优化问题的方法，其适用的问题通常具备以下特性:
问题的最优解是明确的，存在一个候选对象的集合，例如找零问题中的不同面值硬币。
在算法执行过程中，会形成两个子集：已选集，包含已考虑并选中的对象；以及放弃集，包含被考虑过但未选中的对象。
核心是两个评估函数：一个用于检查当前候选对象集合是否构成解决方案，但不考虑是否为最佳解；另一个判断集合是否可以扩展以找到解，同样不考虑最优性。
选择函数则指导算法在剩余候选对象中选取最有可能构成解的对象。
目标函数则是衡量解的质量，算法的目的是找到最优的目标值。
算法的执行过程是递进的：初始时，候选对象集合为空。在每一步中，通过选择函数，算法会选择最有希望的硬币加入已选集。如果添加后导致集合不可行（即无法再添加对象），则该硬币会被放弃；否则，继续添加。这个过程持续进行，直到找到一个可能的解。如果算法设计得当，通常找到的第一个解就接近最优解。
扩展资料
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
