贪心法 PACMANIC WORLDS
贪心法
内容提要 贪心法基本概念 贪心法相关理论 贪心法解题步骤 典型例题 数列极差问题 Dijkstra算法 贪心与剪枝 ·贪心与动态规划 ·贪心启发式方法
内容提要 • 贪心法基本概念 • 贪心法相关理论 • 贪心法解题步骤 • 典型例题 – 数列极差问题 – Dijkstra算法 • 贪心与剪枝 • 贪心与动态规划 • 贪心启发式方法
引例 区间覆盖问题 用来表示x轴上坐标为1-1,订的区间(长 度为1),并给出M(1M≤200)个不同 的整数,表示M个这样的区间。现在要求 画几条线段覆盖住所有的区间,条件是: 每条线段可以任意长,但是要求所画线段 的长度之和最小,并且线段的数目不超过N (1≤N≤50)
引例 • 区间覆盖问题 用i来表示x轴上坐标为[ i - 1, i ]的区间（长 度为1），并给出M（1≤M ≤ 200）个不同 的整数，表示M个这样的区间。现在要求 画几条线段覆盖住所有的区间，条件是： 每条线段可以任意长，但是要求所画线段 的长度之和最小，并且线段的数目不超过N （1 ≤ N ≤ 50）
0 2 3 5 6 8 Q 1011 3 4 M=5 ·8 F2: F3: 7 F4: 6 例如:M=5N=3 方案F4为最佳 事实上,F4即为这个问题的答案
0 1 2 3 4 5 6 7 8 9 10 11 M=5 1 3 4 8 11 F1: F2: F3: F4: 8 8 7 6 例如：M=5,N=3 方案F4为最佳 事实上，F4即为这个问题的答案
分析: N≥M,用M条长度为1的线段 N<M NNN 2k aP第 在N=k-1时最小总长的覆盖方案下,找到被同一条 线段覆盖的间隔最大的两个区间,“贪心”地从间 隔处断开,就可以得到这时总长最小的方案
分析： • N≥M,用M条长度为1的线段 • N＜M – N = 1 – N = 2 – N = k 在N = k – 1时最小总长的覆盖方案下，找到被同一条 线段覆盖的间隔最大的两个区间，“贪心”地从间 隔处断开，就可以得到这时总长最小的方案
内容提要 贪心法基本概念 贪心法相关理论 贪心法解题步骤 典型例题 数列极差问题 Pa第 Dijkstra算法 贪心与剪枝 ·贪心与动态规划 ·贪心启发式方法
内容提要 • 贪心法基本概念 • 贪心法相关理论 • 贪心法解题步骤 • 典型例题 – 数列极差问题 – Dijkstra算法 • 贪心与剪枝 • 贪心与动态规划 • 贪心启发式方法
贪心法基本概念 贪心法 是指从问题的初始状态出发,通过若干次 的贪心选择而得出最优值(或较优解)的一种 解题方法 贪心策略并不是从整体上加以考虑,它所 做出的选择只是在某种意乂上的局部最优 解 ·选择能产生问题最优解的最优量度标准是 使用贪心法的核心问题
贪心法基本概念 • 贪心法： 是指从问题的初始状态出发，通过若干次 的贪心选择而得出最优值(或较优解)的一种 解题方法。 • 贪心策略并不是从整体上加以考虑，它所 做出的选择只是在某种意义上的局部最优 解 • 选择能产生问题最优解的最优量度标准是 使用贪心法的核心问题
内容提要 ·贪心法基本概念 贪心法相关理论 贪心法解题步骤 典型例题 Pa第 数列极差问题 Dijkstra算法 贪心与剪枝 贪心与动态规划 ·贪心启发式方法
内容提要 • 贪心法基本概念 • 贪心法相关理论 • 贪心法解题步骤 • 典型例题 – 数列极差问题 – Dijkstra算法 • 贪心与剪枝 • 贪心与动态规划 • 贪心启发式方法
贪心法相关理论 多阶段决策问题 若干阶段 决策序列 无后向性 Pa算 子问题 与以前决策无关 最优化原理 子策略最优 A
贪心法相关理论 • 多阶段决策问题 – 若干阶段 – 决策序列 • 无后向性 – 子问题 – 与以前决策无关 • 最优化原理 – 子策略最优 A B C D
内容提要 ·贪心法基本概念 /贪心法相关理论 贪心法解题步骤 典型例题 Pa第 数列极差问题 Dijkstra算法 贪心与剪枝 贪心与动态规划 ·贪心启发式方法
内容提要 • 贪心法基本概念 • 贪心法相关理论 • 贪心法解题步骤 • 典型例题 – 数列极差问题 – Dijkstra算法 • 贪心与剪枝 • 贪心与动态规划 • 贪心启发式方法