【算法笔记】贪心法--介绍

  1. 优化子结构

若一个优化问题的优化解包含它的 子问题的优化解,则称其具有优化子结构

  1. 贪心选择性

若一个优化问题的全局优化解可以通过 局部优化选择得到,则该问题称为具有 贪心选择性.

使用贪心算法解决问题时:

  1. 设计贪心方法

  2. 证明贪心法的正确性(有时比设计算法更重要)

例:活动最大相容问题

img
img

(1) 证明优化子结构

活动按照结束时间已经排好序

即证明:设A是问题S的一个优化解且包含活动1,则A-{1}是问题S’(S’中最早的开始时间晚于f1)的优化解

反证法(略)

(2)证明贪心选择性

归纳法(略)