核心思想

贪心算法是一种逐步构建解决方案的算法每一步都选择当前状态下最优的局部选项即“贪心选择”以期望最终获得全局最优解。

贪心算法常用于解决最优化问题。

核心思想

在每一步选择中通过选择当前的局部最优解能够保证最终得到的解是全局最优解。

无后效性No

当前步骤的选择不会影响之后的选择即一个问题的解决可以通过局部的选择逐步逼近全局最优。

最优子结构性质

问题分解将问题分解为若干个子问题。

选择策略为每一步定义贪心选择规则如最大化或最小化。

验证解的可行性每一步选定的解需满足问题的约束条件。

检查最优性选择的局部解是否能保证全局最优。

重复直到完成重复贪心选择直至问题结束。

常见应用场景

给定多个活动的开始和结束时间选择最大数量的活动使得它们互不重叠。

背包问题Knapsack

在分数背包问题中按单位重量价值排序并优先选择单位价值最高的物品。

最小生成树Minimum

简单直观易于实现且解决问题的过程清晰。

高效通过贪心选择通常只需线性或接近线性的时间复杂度。

适用范围广许多经典问题都能用贪心算法求解。

局部最优≠全局最优

activity_selection(start_times,

end_times),

当前活动的开始时间不早于上一个选择活动的结束时间selected.append((start,

end))last_end_time

activity_selection(start_times,

end_times)

贪心算法通过逐步构建解决方案在每一步都选择当前状态下的最优选项是解决许多经典最优化问题的强大工具。

但在应用贪心算法时需要验证问题是否满足最优子结构和贪心选择性质否则可能无法得到正确结果。