从分治策略到动态规划,再到贪心算法

引言

分治, 动态规划和贪心算法, 是算法设计中非常重要的三种思想, 它们各不相同, 却又息息相关. 本文会介绍三种思想之间的共同点和不同之处, 并且列举一些典型算法的例子, 试图探索算法设计的一般思路.

分治策略

我们先来看比较熟悉的快速排序. 快速排序是一个非常典型的分治策略算法. 它采取的方法是把数组中的某一个数移动到数组中的某一个位置, 使得它前面的数都小于它, 它后面的数都大于它. 然后, 对前面的数组和后面的数组做同样的操作. 直到数组全部有序.

下面是快速排序的代码

function qsort(a, l, r)
    if l >= r then return end

    local x = a[r]
    local p = l - 1
    for i = l, r - 1 do
        if a[i] <= x then
            p = p + 1
            a[p], a[i] = a[i], a[p]
        end
    end
    a[p + 1], a[r] = a[r], a[p + 1]

    qsort(a, 1, p)
    qsort(a, p + 2, r)
end

可见, 快速排序的思路是把大问题分解成小问题, 小问题的解法与大问题相同. 这便是分治算法的基本思路. 以上是铺垫, 接下来步入正题

动态规划

现在我们来解决一个调度竞争共享资源的问题：假定有一个n个活动的集合 $S=\\{a_1,a_2,a_3,...,a_n\\}$, 这些活动使用同一个资源(例如一个会议室), 而这个资源在某个时刻只能供一个活动使用. 每个活动 $a_i$ 都有一个开始时间 $s_i$ 和一个结束时间 $f_i$, 其中 $0s_if_i$. 任务 $a_i$ 发生在半开半闭的区间 $[s_i,f_i)$ 期间. 如果两个活动 $a_i$ 和 $a_j$ 满足 $[s_i,f_i)\cap [s_j,f_j)=\varnothing$ 则称 $a_i$ 和 $a_j$ 是兼容的. 我们要解决的问题是给定一个活动集合, 求出最大兼容活动子集的大小. 假定活动已按结束时间递增排序.

例如, 考虑下面的活动集合：

	1	2	3	4	5	6	7	8	9	10	11	12	13
$s_i$	$-\infty$	1	3	0	5	3	5	6	8	8	2	12	$+\infty$
$f_i$	$-\infty$	4	5	6	7	9	9	10	11	12	14	16	$+\infty$

为了方便, 我们设置 $a_1$ 和 $a_{13}$ 是哨兵, 使得我们讨论的活动集合处于 $a_1$ 结束之后, $a_{13}$ 开始之前. 它的最大兼容活动子集是 $\\{a_2,a_5,a_9,a_{12}\\}$ 最大兼容子集的长度是4.

我们尝试把这个问题转换成多个小问题, 小问题又与大问题的解决方式相同. 我们令 $S_{ij}$ 表示在 $a_i$ 结束之后开始, 且在 $a_j$ 开始之前结束的那些活动集合. 那么例子中的问题就可以表示为 $S_{1,13}$, $S_{1,13}=\\{a_i\|2\leqslant i\leqslant 12\\}$. 令 $A_{ij}$ 是 $S_{ij}$ 的一个最大兼容活动子集, 又令 $a_k\in A_{ij}$. 这样, 我们可以得到两个子问题：寻找 $S_{ik}$ 和 $S_{kj}$ 的最大兼容活动子集. 那么 $S_{ik}$ 的最大兼容活动子集 $A_{ik}=A_{ij}\cap S_{ik}$, 同理 $S_{kj}$ 的最大兼容子集 $A_{kj}=A_{ij}\cap S_{kj}$. 因此, 我们有 $A_{ij}=A_{ik}\cup \\{a_k\\}\cup A_{kj}$, $\|A_{ij}\|=\|A_{ik}\|+\|A_{kj}\|+1$.

下图列举了一种极端情况, 即所有的活动都是兼容的.

我们用 $c_{ij}$ 表示 $S_{ij}$ 的最大兼容子集的大小, 可得递归式 $c_{ij}=c_{ik}+c_{kj}+1$. 当然, 由于我们之前是假设的 $a_k\in A_{ij}$, 我们并不知道 $S_{ij}$ 的最大兼容子集包含 $a_k$ . 所以我们需要考察 $S_{ij}$ 的所有活动, 寻找哪个活动可获得最优解. 于是得

\[ c_{ij}=\left\{\begin{matrix} 0 & S_{ij}=\varnothing \\ \underset{a_k\in S_{ij}}{\max}\{c_{ik}+c_{kj}+1\} & S_{ij}\neq \varnothing \end{matrix}\right. \tag{1} \]

根据(1)式我们可以很快地写出一个分治的算法.

function activity_selector(s, f, i, j)
    local max_n = 0
    for k = i + 1, j - 1 do
        if s[k] >= f[i] and f[k] <= s[j] then
            local n = activity_selector(s, f, i, k) + activity_selector(s, f, k, j) + 1
            if n > max_n then
                max_n = n
            end
        end
    end
    return max_n
end

然而, 这个算法是十分低效的.

仔细观察就能发现, 在递归求解的过程中, 函数会不断地求解重复的问题！我们在函数开始的时候加个打印 print(i, j) 就更明显了：

以极端情况下的 $S_{1,4}$ 为例, 画出递归树：

可以看到, 我们在反复求解相同的问题. 这种现象我们称之为子问题重叠. 事实上, 使用分治算法的活动选择问题的时间复杂度是指数级的.

那么, 我们怎样解决子问题重叠带来的问题呢？最简单的办法是定义一个变量, 把每次算的结果都存起来, 每次计算之前, 先去这个这个变量里找, 如果找得到, 就直接返回结果, 否则才去计算. 代码如下：

local save = {}
function set(i, j, n)
    if not save[i] then save[i] = {} end
    save[i][j] = n
end
function get(i, j)
    if not save[i] then return nil end
    return save[i][j]
end

function activity_selector(s, f, i, j)
    local m = get(i, j)
    if m then return m end

    local max_n = 0
    for k = i + 1, j - 1 do
        if s[k] >= f[i] and f[k] <= s[j] then
            local n = activity_selector(s, f, i, k) + activity_selector(s, f, k, j) + 1
            if n > max_n then
                max_n = n
            end
        end
    end
    set(i, j, max_n)
    return max_n
end

我们可以跟进一步, 与其每次判断某个子问题是否被求解过, 不如安排一种顺序, 先解小问题, 再解大问题, 使得所有问题所依赖的子问题都已经被求解过. 通过观察递归树, 序列$\left< S_{1,2},S_{2,3},S_{1,3},S_{3,4},S_{1,4} \right>$ 中的每一个问题的子问题都排在它的前面. 如果我们这样安排解决问题的顺序, 就可以去掉递归和判断, 更加高效地解决问题：


function activity_selector(s, f)
    local c = {}
    for i = 1, #s do
        for j = 1, #s do
            if not c[i] then c[i] = {} end
            c[i][j] = 0
        end
    end

    for j = 2, #s do
        for i = j - 1, 1, -1 do
            local max_n = 0
            for k = i + 1, j - 1 do
                if s[k] >= f[i] and f[k] <= s[j] then
                    local n = c[i][k] + c[k][j] + 1
                    if max_n < n then
                        max_n = n
                    end
                end
            end
            c[i][j] = max_n
        end
    end
    return c[1][#s]
end

可以看到, 高亮的那几行代码与分治算法几乎是一模一样的, 不同的是, 分治算法所依赖的子问题的解尚未求得, 每次都要递归地求解, 而这个算法所依赖的子问题的解却早已求出, 可以在数组c中直接取到. 与分治的自顶向下不同, 这种自底向上的算法就叫动态规划.

动态规划的核心思想就是通过自底向上的方法, 使得大问题所依赖的子问题总是在大问题求解之前被解决. 它解决的核心问题就是分治中子问题重叠的问题.

贪心算法

上文中, 分治和动态规划算法做的最主要的事情是什么？自然是高亮的那几行–在做一个选择, 也就是(1)式中的那个最大的选择. 就如前文所说, 我们并不知道 $S_{ij}$ 的最大兼容子集包含 $a_k$ . 所以我们需要考察 $S_{ij}$ 的所有活动, 寻找哪个活动可获得最优解. 其实我们可以加点输出, 看看它做的那个选择是什么：

function activity_selector(s, f)
    local c = {}
    -- ...

    for j = 2, #s do
        for i = j - 1, 1, -1 do
            local max_n = 0
            local save_k
            for k = i + 1, j - 1 do
                if s[k] >= f[i] and f[k] <= s[j] then
                    local n = c[i][k] + c[k][j] + 1
                    if max_n < n then
                        max_n = n
                        save_k = k
                    end
                end
            end
            if max_n ~= 0 then print(i, j, save_k) end
            c[i][j] = max_n
        end
    end
    return c[1][#s]
end

输出如下：

可以看到, $a_k$ 始终是 $S_{ij}$ 中 $f_j$ 最小即最早结束的活动. 从直观上, 我们应该选择这样一个活动, 选出它后剩下的资源应能被尽量多的其他任务所用. 因此, 直觉告诉我们, 应该选择S中最早结束的活动, 因为它剩下的资源可供它之后尽量多的活动使用.

令 $S_k=\\{a_i\|a_i\in S,s_i\geqslant f_k\\}$ 为在 $a_k$ 结束后开始的任务集合. 我们选择一个结束时间最短的活动 $a_k$ 然后在 $S_k$ 中做同样的操作. 代码如下：

function activity_selector(s, f, k)
    local m = k + 1
    while m <= #s and s[m] < f[k] do
        m = m + 1
    end
    if m <= #s then
        return activity_selector(s, f, m) + 1
    else
        return 0
    end
end

在这个算法中, 我们直接选择了最早结束的活动作为 $a_k$, 而不需要像动态规划一样, 先要解决所有的子问题, 然后才做出一个选择.

贪心算法算法通常要比动态规划快得多, 实现也要简单的多. 这个例子中, 使用贪心算法, 它的时间复杂度仅为$O(n)$. 但要知道每个贪心算法之下, 几乎总有一个更繁琐的动态规划算法.

总结

分治：即分而治之. 把一个大问题分解成多个小问题, 小问题的解决方法又与大问题相同.
动态规划：也是把一个大问题分解成多个小问题, 小问题的解决方法与大问题相同；不同的是, 在分解过程中会产生重复的小问题, 动态规划所做的, 就是安排一个巧妙的顺序, 使得重复的小问题不会被重复计算.
贪心：也是把一个大问题分解成多个小问题, 小问题的解决方法与大问题相同；不同的是, 它通过多次做出一个巧妙的选择(贪心选择), 使得不需要求解所有的子问题, 只需要求解一部分子问题(通常是一小部分)就能够求解出大问题.

#algorithms #featured

从分治策略到动态规划,再到贪心算法

https://luyuhuang.tech/2018/02/09/dc-dp-ga.html

Author

Luyu Huang

Posted on

February 9, 2018

Licensed under

四元数描述旋转 Previous

避免使用无符号数 Next

	1	2	3	4	5	6	7	8	9	10	11	12	13
\(s_i\)	\(-\infty\)	1	3	0	5	3	5	6	8	8	2	12	\(+\infty\)
\(f_i\)	\(-\infty\)	4	5	6	7	9	9	10	11	12	14	16	\(+\infty\)