贪心法得到近似解 贪心法得到近似解 ■地图着色问题贪心选择 ■地图着色问题 Whle存在未被着色的区域 按1,2,345顺序进行贪心选择 选择一种新颜色C 选择一个未着色的区域A,用C着色 考察其他所有未着色区域,如果不与着色 为C的区域相邻,就用C着色 ■最优解应该为 贪心法、动态规划与回溯 习题 动态规划 贪心法 安装雷达 使用条件优化原则 多米诺性质 货心选择 多步判断 多步判断 区间覆 拆墙 选择依据子问题结果 约束条件和界 计算过程看子问题结果选择|选择后生成子问题选择后生成子问题 钓鱼 一个和多个最优解一个最优和近似解 关键问题遂推方程 贪心选择性质证明 空问复杂度高 时向复杂度高 近似解的误差估计 安装雷达1328 安装雷达1328 ■海上有N个扫描点 ■对什么进行贪心选择?怎么排序? 雷达扫描范围d 按横坐标排序从左到右扫描? ■至少要安装几个雷达才能将N个点都覆盖 ++9 ,.个4 贪心法得到近似解 „ 地图着色问题贪心选择 „ While 存在未被着色的区域 „ 选择一种新颜色C „ 选择一个未着色的区域A，用C着色 „ 考察其他所有未着色区域，如果不与着色 为C的区域相邻，就用C着色 贪心法得到近似解 „ 地图着色问题 „ 按1,2,3,4,5顺序进行贪心选择 „ 最优解应该为 1 5 2 4 3 1 5 2 4 3 贪心法、动态规划与回溯 贪心选择性质证明 近似解的误差估计 设定代价函数 时间复杂度高 递推方程 空间复杂度高 关键问题 解 一个最优解 一个和多个最优解 一个最优和近似解 数据结构 二维表 树、队列 线性表 选择后生成子问题 自顶向下 选择后生成子问题 自顶向下 看子问题结果选择 自底向上 计算过程 选择依据 子问题结果 约束条件和界 局部最优性质 贪心选择 优化原则 多步判断 多米诺性质 多步判断 优化原则 多步判断 使用条件 技术 动态规划 分支估界 贪心法 习题 „ 安装雷达 „ 区间覆盖 „ 拆墙 „ 钓鱼 安装雷达 1328 „ 海上有N个扫描点 „ 雷达扫描范围d „ 至少要安装几个雷达才能将N个点都覆盖 住 安装雷达 1328 „ 对什么进行贪心选择？怎么排序？ „ 按横坐标排序从左到右扫描？