贪心算法和B树

贪心算法

动态规划是一种解决问题的通用方法，在求解最优化问题的时候，动态规划能够综合考虑到各种情况然后做出最优的选择。可是，对于一些特殊的问题，在从子问题中做出选择时，可以不用考虑所有的子问题，而只需要考虑一个子问题，因为选择这个子问题一定可以达到一个最优解，在这种情况下，就可以采用贪心算法来解决。贪心算法的好处在于，不需要考虑所有的子问题，只需要考虑一种情况，这时求解的子问题的数目就减少了，同时，可以采用一种自顶向下的方法解决问题，逐步地把问题转化为更小的子问题，直到可以轻易解决。

从动态规划到贪心

书上给出了一个这样的例子来说明从动态规划算法转化到贪心算法。

有n个活动组成集合 $S = \{a_1, a_2, ..., a_n\}$ ，它们需要占用同一个资源，这个资源在同一个时间只能被一个活动占用，每一个活动 $a_i$ 使用资源的起始时间和结束时间分别为 $s_n, f_n$ ，如果区间 $[s_i, f_i)$ 与区间 $[s_j, f_j)$ 不重叠，就称活动 $a_i$ 与活动 $a_j$ 是兼容的，求S的一个由互相兼容的活动组成的最大子集，假设活动已经按结束时间排好序。

对于这个问题，可以定义如下子问题 $S_{ij}$ ，表示从S的子集 $S_{ij}$ 中得到的最大兼容子集，其中 $S_{ij} = \{ a_k \in S: s_k \geq f_i and f_k < s_j \}$ ，也就是说， $S_{ij}$ 是由所有在 $a_i$ 结束之后开始，在 $a_j$ 开始之前结束的活动组成的集合。通过定义这样一个子问题，就可以很容易地得出如下递推公式，

$A_{ij} = A_{ik} \bigcup \{a_k\} \bigcup A_{kj}, 其中A_{ij}表示子问题S_{ij}的解$

从而利用动态规划解决这个问题。

然而，动态规划并不是一个最优的解法，因为要求解的子问题的个数为 $O(n^2)$ 个，而且求解每个子问题时选择的个数也有 $O(n)$ 个，这就导致了通过动态规划求解问题所需的复杂度为 $O(n^3)$ 。

如果采用贪心的算法，每次通过选取 $S_{ij}$ 中具有最早结束时间的活动 $a_m$ 作为划分元素的话，那么就可以通过

$A_{ij} = A_{im} \bigcup \{a_m\} \bigcup A_{mj}$

得到一个最优的解，而不用考虑其它元素作为划分元素时的子问题。

定义函数递归函数RECURSIVE-ACTIVITY-SELECTOR(S, f, i, n)求取子问题 $S_{i(n+1)}$ 的解，伪代码如下：

def RECURSIVE-ACTIVITY-SELECTOR(s, f, i, n)
    m := i + 1
    while m <= n and s[m] < f[i]
        do m := m + 1
    if m <= n
        then return {a[m]} union RECURSIVE-ACTIVITY-SELECTOR(s, f, m, n)
        else return EMPTY_SET

求解原问题就可以通过调用RECURSIVE-ACTIVITY-SELECTOR(s, f, 0, n)来完成。从代码中可以看出，每个活动都只被检查过一次，如果函数调用的时间可以忽略不计的话( 这个递归地算法可以通过迭代来实现，所以算法本身可以不用考虑这个问题)，那么整个算法的时间复杂度为 $\Theta(n)$ 。相比于动态规划，效率要提高很多。

关于这个问题的几点解释

关于为什么可以将 $a_m$ 选作分界元素需要说明两点：
1. 一定有某一个最大兼容子集包含元素 $a_m$ ，也就是说，如果要挑选出一些元素组成最大兼容子集，那么先把 $a_m$ 选中放入这个集合中肯定能导致一个最优解。关于这种命题的证明，普遍的方式是假设有一个最优解没有包含这个元素，那么把这个元素和某个元素替换后会导致一个不会比原来差的解。书上也是采取这样的证明方式。以后在证明最小生成树的贪心算法时也是采取这样的方式。
2. 把 $a_m$ 放入最大兼容子集后，这个最大兼容子集的其余元素一定是子问题 $S_{mj}$ 的一个解。这个比较好证明，只需要证明对于任意和 $a_m$ 兼容的元素 $a_k$ , 一定有 $s_k \geq f_m$ 即可。
有了这两点，就能得出：

也就是将 $a_m$ 选作分界元素, 同时可以不需要求解 $S_{im}$ 。
需要注意的是 $S_{ij} \neq \{a_{i+1}, a_{i+2}, ..., a_{j-1} \}$ ，这个等式只有在 $i=0, j=n+1$ 时成立，但是从代码中我们可以看到，在调用RECURSIVE-ACTIVITY-SELECTOR(S, f, i, n)时，此时可能被添加进最大兼容子集的元素集合是 $\{a_{i+1}, a_{i+2}, ..., a_{n} \}$ , 而不是 $S_{i(n+1)}$ ，然而这并不会导致什么问题，因为在选取 $a_m$ 时，已经过滤掉了开始时间小于 $f_i$ 的元素，随着迭代次数的加深，那些开始时间小于 $f_i$ 的元素也会被过滤掉，因为开始时间小于 $f_i$ 也一定会小于 $f_m$ ，在更深的迭代时同样会被过滤。

采取这样的方式实现代码能够降低时间和空间的复杂度，因为如果每次求解子问题时都需要求出 $S_{ij}$ 这个集合的话，需要 $O(n)$ 的时间来求出，同时也需要一个数组来保存这个子集，显然不如书上的这个实现简单。
这个问题如果用动态规划的话可以采用另外一种思路，令c[i]表示集合 $\{a_1, ..., a_i \}$ 中，包含元素 $a[i]$ 的最大兼容子集的元素个数，那么有如下递归公式成立
$c[i] = \max \{\max_{j < i}_{s_i > f_j } \{c[j] + 1\}, 1 \}$
利用这个递归公式求解的话，时间复杂度可以降到 $O(n^2)$ 。

贪心算法的基本条件

总的来说，贪心算法比动态规划效率要高，实现起来也相对简单一些，同时也是一般人比较容易想到的算法。但是这并不意味着它比较简单，因为并不是所有的问题都能够使用贪心法得到解决，它比动态规划有更多的限制条件，它必须满足两个基本条件：

贪心选择性质：一个全局最优解可以通过局部最有解得到。这是贪心算法与动态规划的不同之处。证明贪心选择性质一般用上面提到的修改最优解，使其包含局部最优解，然后得到一个不差于最优解的解，就能证明。
最优子结构，这和动态规划一样，可以通过”剪切，粘贴”的方法证明。

哈夫曼编码

贪心算法可以用于求解很多问题，在图算法中的最小生成树算法，单源最短路径算法等都是利用贪心法解决，关于这些算法，我在图算法时再详细阐述，现在说另外一个比较典型的贪心算法的例子。

哈夫曼编码，这个基本是任何算法书都需要提及的使用贪心算法的例子。有n个不同字符，知道它们的出现的出现次数，如何设计一个前缀编码使得整个文件的编码最短。利用一个优先级队列，每次把队列的频率最小的两个元素出队，组成一个新的元素然后入队，直到队列只剩一个元素为止。这个算法贪心选择性质的证明也比较简单。

另一种贪心算法

前面说到的贪心算法都是用于求解最优化问题，在应用贪心算法的时候，看问题是否具备贪心选择的性质，如果具备，就通过贪心法求解。有另外一种问题也可以归入贪心算法的范畴，这样的问题不是求最优解，而只是需要正确地的解决某一个问题，在这种问题中，没有最优解可言，只是求出问题的正确的解就可以。在解决问题的过程中，可能会有很多选择，类似于要不要选择某个元素，要不要把某个变量设成True，这许多的选择组合起来就会导致解有很多种可能性，目的就在于从这许多的解中找出满足指定条件的一个解，如果存在的话。这就类似于走迷宫，有许多的分叉路口，就很多种走法，从这些走法中找出一个能走到出口的就可以。

对于这些问题，暴力搜索每一种可能性显然不是一种好方法，动态规划也可以用于解决这样的问题，在解决一个问题时利用一个子问题是否满足条件来决定当前的问题是否满足条件。而贪心算法在解决这种问题时采取了一种更加直观的想法: 必须要做某一个选择，否则就是不满足条件的解。如果问题具有这样的性质，就可以很容易地选出一个解，因此每次的选择都是唯一的，然后再看这个选择是否满足条件即可。如果满足条件，那么就找到了一个解，如果不满足，那么就没有解，因为其他的解肯定不满足条件。下面通过Horn公式来更详细的说明。

在Horn公式中，我们指定了一些布尔变量(比如x，y, z)必须满足的性质，通过两种公式给出:

蕴含式：在这种公式中，左边为合取范式，右边为单一变量, 所有变量必须不含否定，比如 $(z \bigwedge w) \Longrightarrow u$ 或者 $\Longrightarrow x$ , 而 $(z \bigwedge \bar w) \Longrightarrow u$ 就不是这种蕴含式
完全由变量的否定组成的析取范式, 比如 $(\bar u \bigvee \bar v \bigvee \bar y )$ 。

问题是给定一个Horn公式，确定是否可以给公式中出现的变量赋予合适的布尔值，使所有的这些公式都能得到满足。很显然，要满足蕴含式，需要要把一些变量设为True, 而要满足析取范式，需要把一些变量设为False。对于每一个变量，赋值的方式都有两种，遍历所有的可能性显然是效率不高的。

贪心算法通过这样的思路来解决：

首先把变量都设为False，
如果有蕴含式不满足，就把蕴含式右边的变量设成True，然后继续这个步骤直到所有的蕴含式都满足为止, 否则到步骤3。
查看是否有析取范式不满足，如果全满足，那么就找到了一个解，否则，无解。

说明两点：

为什么这个算法是正确的。如果找到了一个解，显然是正确的。如果没找到解，为什么就无解呢？因为前面的把变量设为True是“必须”的，也就是说，一个变量被设为True，那么在任何正确的解中，它必须被设为True，所有在这些必须的步骤都完成之后，如果不满足条件，也就没有解可以满足条件了。
重复检查所有蕴含式是否满足的次数的不超过n+1次，其中n为变量的个数。因为除了第一次检查，其余每一次检查都是因为前一次有变量被设为True， (否则如果没有变量被设为True, 那么所有的蕴含式都满足，就不会再去检查了), 而变量被设为True的次数不超过n次，所以检查次数不超过n+1次，这就保证了检查所有蕴含式是否满足并不是一个复杂度非常高的过程。

在这种贪心算法中，解决思路是找出那些必须要执行的步骤，一步一步，将问题简化，最终解决。

B树

B树也是一种平衡地二叉查找树，类似于红黑树，它也能够支持动态地插入，删除和查找数据。 B树主要用于保存数据到磁盘中，比如很多数据库的索引就是通过B树进行保存。由于磁盘的读取速度相对于内存要慢得多，所以尽量地减少IO的次数显得非常重要， B树也正是实现了这样的思想，B树的深度不会太深，这样查找数据所需要遍历的节点数就会很少，相应的IO次数也会减少。

在B树中，一个非根的节点至少包含t-1个关键字，这样每一个非根的节点就至少有t个子女，这样一棵包含n个关键字的B树的高度h至多为 $\log t \frac{n+1}{2}$ 。但是一个节点包含的关键字又不能太多，一方面是因为一次IO只能读取指定数量的字节，另一方面太多的关键字会导致定位一个关键字比较耗时，所以B树的每个节点包含至多2t-1个关键字。

这些性质能够保证B树查找的性能，但是在插入和删除的时候就需要维护这些性质。具体表现在：

当插入一个关键字到一个已经满了节点（包含2t-1个关键字），就需要把这个节点分裂成两个，同时把这个节点中间关键字插入到它的父节点，这样可能会导致父节点的关键字超过2t-1，所以需要一直向上到根来进行维护。
当删除一个关键字时，会导致只有t-1个关键字的节点不满足性质，这时可以通过向它的兄弟“借”一个关键字，如果兄弟包含至少t个关键字的话，否则，就和兄弟合并，然后从父节点删除一个关键字，同样的，此时需要一直向上到根来进行维护。

书上在插入和删除节点的时候为了避免向上过滤来进行维护，在遍历到某一个节点的时候，就把性质维护好，这样当一个节点遍历到的时候，就能保证它的父节点不需要再去维护了。这样的方法，对于插入还好，对于删除操作就显得有点复杂，考虑了好多种情况，我觉得还是向上过滤进行维护比较好，并没有增加复杂度。

Chouqin's Blog

A blog for hackers.