贪心法

贪心法的例子：活动选择问题

贪心算法的特点

设计要素：
(1) 贪心法适用于组合优化问题.
(2) 求解过程是多步判断过程，最终的判断序列对应于问题的最优解.
(3) 依据某种“短视的”贪心选择性质判断，性质好坏决定算法的成败.
(4) 贪心法必须进行正确性证明.
(5) 证明贪心法不正确的技巧：举反例.

贪心法的优势：算法简单，时间和空间复杂性低

贪心法正确性 证明:活动选择

算法正确性归纳证明

证明步骤：

1. 叙述一个有关自然数n的命题，该命题断定该贪心策略的执行最终将导致最优解. 其中自然数 n 可以代表算法步数或者问题规模 .
2. 证明命题对所有的自然数为真 .
   归纳基础(从最小实例规模开始)
   归纳步骤(第一或第二数学归纳法)

活动选择算法的命题

命题
算法 Select执行到第 k 步, 选择 k 项活动
$i_1 = 1, i_2 , … , i_k$i1​=1,i2​,…,ik​
则存在最优解 A包含活动 $i_1 = 1, i_2 , … , i_k$i1​=1,i2​,…,ik​.

根据上述命题：对于任何 k，算法前 k步的选择都将导致最优解，至多到第n 步将得到问题实例的最优解

小结

• 贪心法正确性证明方法：数学归纳法
第一数学归纳法、第二数学归纳法

• 活动选择问题的贪心法证明：
叙述一个涉及步数的算法正确性命题
证明归纳基础
证明归纳步骤

最优装载问题

算法设计

• 贪心策略：轻者优先
• 算法设计：
将集装箱排序，使得
$w_1 ≤ w_2 ≤ ... ≤ w_n$w1​≤w2​≤...≤wn​

按照标号从小到大装箱，直到装入下一个箱子将使得集装箱总重超过轮船装载重量限制，则停止.

正确性证明思路

• 命题：对装载问题任何规模为 n 的输入实例，算法得到最优解.

• 设集装箱从轻到重记为1, 2, … , n.
归纳基础 证明对任何只含 1个箱子的输入实例，贪心法得到最优解.
显然正确.

• 归纳步骤 证明：假设对于任何n个箱子的输入实例贪心法都能得到最优解，那么对于任何n+1个箱子的输入实例贪心法也得到最优解.

小结

• 装载问题是0-1背包的子问题 (每件物品重量为1)，NP难的问题存在多项式时间可解的子问题.
• 贪心法证明：对规模归纳

最小延迟调度问题

小结

• 分析算法解与一般最优解的区别,找到把一般解改造成算法解的一系列操作(替换成份、交换次序)贪心法正确性证明方法：交换论证
• 证明操作步数有限
• 证明每步操作后的得到解仍旧保持最优

得不到最优解的处理方法

• 输入参数分析：
考虑输入参数在什么取值范围内使用贪心法可以得到最优解
• 误差分析：
估计贪心法——近似算法所得到的解与最优解的误差（对所有的输入实例在最坏情况下误差的上界）

小结

• 贪心策略不一定得到最优解，在这种情况下可以有两种处理方法：
(1) 参数化分析：分析参数取什么值可得到最优解
(2) 估计贪心法得到的解在最坏情况下与最优解的误差

• 一个参数化分析的例子:找零钱问题