基础算法--贪心_数学归纳法证明贪心算法

基础算法–贪心

上一节中我提到的搜索是遍历状态空间中的所有解。而贪心(Greedy Algorithm)是沿着一条看上去最优的路径走到底，永不反悔

• 贪心过程
  • 从初始状态出发
  • 如果到达终止状态，则输出对应解并结束；否则，评估当前状态的所有后继状态，并选择一个最优的后继状态，更新当前状态
• 贪心选择性质
  • 可以通过局部最优的贪心决策来构造全局最优解，无需考虑后效性
• 一个问题具有最优子结构时，贪心算法往往效果比较好
  • 如果一个问题具有最优子结构，那么整个问题的最优解可以由子问题的最优解构造得到

证明贪心算法的正确性

归纳法

首先证明边界情况是正确，然后归纳证明一般的情况。假定给一个序列$a_1,a_2,a_3,...,a_n$求出一个区间$[l,r]$，使得$a_l+...+a_r$最大。这里我们考虑使用归纳法证明最大子段和的贪心算法

• 贪心算法，从左到右扫描，维护当前$a_1,...,a_i$的最大后缀和
  • 加上新的一项$a_{i+1}$时，如果当前的最大后缀和加上$a_{i+1}$小于$0$，则抛弃维护的后缀，并将当前最大后缀和更新为$0$；否则当前最大后缀和为$a_1,...,a_i$的最大后缀和加上$a_{i+1}$
  • 用当前的最大后缀和更新答案
• 当$n=1$的时候显然成立
• 已知该算法对$a_1,a_2,a_3,...,a_n$能求出最优解，加入$a_{n+1}$时
  • 新序列的最大子段和要么是原序列的最大子段和，要么必须包含$a_{n+1}$。而后者是对应最大后缀和，因此我们只需在原序列的最大子段和与包含$a_{n+1}$的最大子段和两者中取最大值即可
• 因此针对上述问题我们可以使用贪心算法得到最优解

void greedy_algorithm(std::vector<int> &nums) {
    int maxSum = 0;
    int subSum = 0;
    int i = 0;
    while (i < nums.size()) {
        subSum += nums[i];
        if (subSum > 0) {
            maxSum = subSum > maxSum ? subSum : maxSum;
        } else {
            subSum = 0;
        }
        ++i;
    }
    std::cout << "maxSum = " << maxSum << std::endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

反证法

先依靠贪心算法得出最优解，再证明：将任意步骤的决策替换为任意的其他选择，最后结果都不可能达到更优。假定有$n$个物品各自的重量，背包负重上限为$N$，要求在不超过负重上限的情况下，尽可能的多带物品

• 先收我们利用贪心算法得出的最优解为$[n_1,n_2,n_3,...,n_x]$，现用$m$替换 $n_1$（$n_1$ 已是当前最轻，故$m>n1$），证明能否得到更优解 $[m,n_2,n_3,...,n_x,n_y]$，即比原来最优解多带一个物品$n_y$
• $[n_m,n_2,n_3,...,n_x,n_y]$前$x$项之和必定大于$[n_1,n_2,n_3,...,n_x]$之和，且$[n_m,n_2,n_3,...,n_x,n_y]$还多了一项$n_y$都没有超限，说明$[n_1,n_2,n_3,...,n_x,n_y]$也必定不会超限，原最优解应为$[n_1,n_2,n_3,...,n_x]$与题设相悖，故反证错误，不存在这样的替换方法。即：替换最优解任意项后，都无法达到更优，得证

贪心算法与动态规划

如果了解动态规划的朋友，可能会觉得这两个算法很像。这里我们先简单的做一些对比，等后续讲解动态规划的时候，再来重提两个算法的区别

案例

埃及分数

给出一个分子分母分别为$mol$和$den$构成的分数，要求将其分解为一系列互不相同的单位分数（分子为$1$），并且要求分解的单位分数越少越好，如果单位分子数量一样，那么最小的单位分数越大越好

int comm_factor(int m, int n) {
    if (n > m) std::swap(m, n);
    int z = n;
    while (m % n != 0) {
        z = m % n;
        m = n;
        n = z;
    }
    return z;
}

void egyptian_fractions(int mol, int den) {
    int n = 0, r = 0;
    std::cout << mol << "/" << den << " = ";
    do {
        n = den / mol + 1;
        std::cout << "1/" << n << " + ";
        mol = mol * n - den;
        den = den * n;
        r = comm_factor(den, mol);
        den /= r;
        mol /= r;
    } while (mol > 1);
    std::cout << "1/" << den << std::endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Huffman Tree

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree) — 百度百科

假定有$n$个权值，则构造出的哈夫曼树有$n$个叶子结点。 $n$个权值分别设为$w_1$、$w_2$、…、$w_n$，则哈夫曼树的构造规则为：

• 将$w_1$、$w_2$、…，$w_n$看成是有$n$棵树的森林(每棵树仅有一个结点)
• 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和
• 从森林中删除选取的两棵树，并将新树加入森林。重复上面两步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树

代码相对简单，这里就不再详细展开了