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

引言

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

分治策略

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

qsort

下面是快速排序的代码

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个活动的集合 , 这些活动使用同一个资源(例如一个会议室), 而这个资源在某个时刻只能供一个活动使用. 每个活动 都有一个开始时间 和一个结束时间 , 其中 . 任务 发生在半开半闭的区间 期间. 如果两个活动 和 满足 则称 和 是兼容的. 我们要解决的问题是给定一个活动集合, 求出最大兼容活动子集的大小. 假定活动已按结束时间递增排序.

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

	1	2	3	4	5	6	7	8	9	10	11	12	13
		1	3	0	5	3	5	6	8	8	2	12
		4	5	6	7	9	9	10	11	12	14	16

为了方便, 我们设置 和 是哨兵, 使得我们讨论的活动集合处于 结束之后, 开始之前. 它的最大兼容活动子集是 最大兼容子集的长度是4.

我们尝试把这个问题转换成多个小问题, 小问题又与大问题的解决方式相同. 我们令 表示在 结束之后开始, 且在 开始之前结束的那些活动集合. 那么例子中的问题就可以表示为 , . 令 是 的一个最大兼容活动子集, 又令 . 这样, 我们可以得到两个子问题：寻找 和 的最大兼容活动子集. 那么 的最大兼容活动子集 , 同理 的最大兼容子集 . 因此, 我们有 , .

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

compatibility

我们用 表示 的最大兼容子集的大小, 可得递归式 . 当然, 由于我们之前是假设的 , 我们并不知道 的最大兼容子集包含 . 所以我们需要考察 的所有活动, 寻找哪个活动可获得最优解. 于是得

根据(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) 就更明显了：

print i,j

以极端情况下的 为例, 画出递归树：

tree

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

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

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

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

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)式中的那个最大的选择. 就如前文所说, 我们并不知道 的最大兼容子集包含 . 所以我们需要考察 的所有活动, 寻找哪个活动可获得最优解. 其实我们可以加点输出, 看看它做的那个选择是什么：

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

输出如下：

print i,j,save_k

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

令 为在 结束后开始的任务集合. 我们选择一个结束时间最短的活动 然后在 中做同样的操作. 代码如下：

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

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

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

总结

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