【游戏算法】 - 贪心算法

贪心算法

贪心算法是一种分阶段决策策略，在每一步选择中，仅考虑当前状态的局部最优解，通过迭代累积这些局部最优解，期望得到全局最优解。其核心特征包括：

无后效性：当前决策不影响后续状态。
贪心选择性质：每一步的最优解不依赖于未来决策或子问题的解。
最优子结构：问题的最优解包含其子问题的最优解。

适用场景

贪心算法适用于以下问题：

• 局部最优解能推导全局最优解（如区间调度问题）。
• 需要实时计算且对性能要求高（如游戏中的AI寻路）。
• 问题规模较大，无法通过动态规划或回溯法解决。

经典应用

资源分配

贪心算法在资源分配问题中表现尤为突出，例如分配有限的资源（如金币、道具）以最大化收益或最小化损失。

路劲规划

在游戏AI中，角色需要快速找到从起点到终点的可行路径。贪心算法的局部最优选择（如每次选择离终点最近的方向）可以快速生成一条近似最优路径，尽管可能不是全局最优，但能显著提升计算效率。

贪心算法的陷阱与注意事项

局部最优 ≠ 全局最优

贪心算法的局限性在于可能无法得到全局最优解。例如，在硬币找零问题中，若硬币面额为 [1, 3, 4]，贪心算法无法正确找零 6（会选 4+1+1=6，而最优解是 3+3=6）。

正确性证明

贪心算法的正确性需通过数学归纳法或反证法严格证明。例如，跳跃游戏的贪心策略可通过以下逻辑验证：

• 若 i <= maxIndex，则 i 是可达的。
• maxIndex 的更新确保了所有可达位置都被覆盖。

性能优化

贪心算法通常具有 O(n) 或 O(n log n) 的时间复杂度，适合大规模数据。例如，区间调度问题中，按结束时间排序后贪心选择可将时间复杂度降至 O(n log n)。

参考链接

第 15 章   贪心 - Hello 算法