内容提要 贪心法基本概念 贪心法相关理论 贪心法解题步骤 典型例题 数列极差问题 Pa第 Dijkstra算法 贪心与剪枝 ·贪心与动态规划 ·贪心启发式方法
内容提要 • 贪心法基本概念 • 贪心法相关理论 • 贪心法解题步骤 • 典型例题 – 数列极差问题 – Dijkstra算法 • 贪心与剪枝 • 贪心与动态规划 • 贪心启发式方法
贪心法基本概念 贪心法 是指从问题的初始状态出发,通过若干次 的贪心选择而得出最优值(或较优解)的一种 解题方法 贪心策略并不是从整体上加以考虑,它所 做出的选择只是在某种意乂上的局部最优 解 ·选择能产生问题最优解的最优量度标准是 使用贪心法的核心问题
贪心法基本概念 • 贪心法： 是指从问题的初始状态出发，通过若干次 的贪心选择而得出最优值(或较优解)的一种 解题方法。 • 贪心策略并不是从整体上加以考虑，它所 做出的选择只是在某种意义上的局部最优 解 • 选择能产生问题最优解的最优量度标准是 使用贪心法的核心问题
内容提要 ·贪心法基本概念 贪心法相关理论 贪心法解题步骤 典型例题 Pa第 数列极差问题 Dijkstra算法 贪心与剪枝 贪心与动态规划 ·贪心启发式方法
内容提要 • 贪心法基本概念 • 贪心法相关理论 • 贪心法解题步骤 • 典型例题 – 数列极差问题 – Dijkstra算法 • 贪心与剪枝 • 贪心与动态规划 • 贪心启发式方法
贪心法相关理论 多阶段决策问题 若干阶段 决策序列 无后向性 Pa算 子问题 与以前决策无关 最优化原理 子策略最优 A
贪心法相关理论 • 多阶段决策问题 – 若干阶段 – 决策序列 • 无后向性 – 子问题 – 与以前决策无关 • 最优化原理 – 子策略最优 A B C D
内容提要 ·贪心法基本概念 /贪心法相关理论 贪心法解题步骤 典型例题 Pa第 数列极差问题 Dijkstra算法 贪心与剪枝 贪心与动态规划 ·贪心启发式方法
内容提要 • 贪心法基本概念 • 贪心法相关理论 • 贪心法解题步骤 • 典型例题 – 数列极差问题 – Dijkstra算法 • 贪心与剪枝 • 贪心与动态规划 • 贪心启发式方法