斯坦福 算法2 第三周笔记

来自斯坦福网站的Algorithms: Design and Analysis，与目前coursera上的版本内容没有变化，不过时间安排略有不同。

1. Introduction to Dynamic Programming

定义了一个independent set的问题。相当于是一个非负数组，取数组中不相邻的元素相加，求这些元素最大和。

使用暴力解法需要平方复杂度，但是如果使用之前讲的分治法在组合的那步会有问题。

于是我们来分析一下这个问题的最优解会是怎样的结构，或许能够利用解法的结构来减少需要搜索的候选答案。

于是我们就发现，如果将图中最后一个结点表示为$v_{n}$vn​，那么最后的解$S$S就有包括$v_{n}$vn​与不包括这两种情况。而且两种情况里分别还可以知道更小的$G'$G′或者$G''$G′′最优解与$S$S之间的关系：

于是我们发现最终的答案S与更小的图的解之间的关系：

如果我们已知了这两个解，那么只需要比较一下取较大的一个就得到了最终的$S$S。假如我们按照这个思路进行递归，就可以直接得到答案$S$S。但是这么做的时间复杂度是$2^{n}$2n的。

实际上，对于一个有n个点的图来说，递归真正需要得到的中间结果只有n个，如果将前面求得的结果存起来，那么整个的算法可以在$O(n)$O(n)时间内解决。这个方法叫做memoization。

于是将从结点1到结点i组成的图叫做$G_{i}$Gi​，用一个数组的元素$A[i]$A[i]表示$G_{i}$Gi​的最优解的权重和，我们就有如下算法：

不过我们需要知道的不仅仅是权重和，还需要得到这个集合的组成元素，因此需要根据结果重建得到需要知道的集合。根据数组A的结果可以很容易得到。

这种解法就叫做动态规划。动态规划有三个重要的组成部分：

2. The Knapsack Problem

背包问题。每个石头有重量$w_{i}$wi​与价值$v_{i}$vi​，背包有称重上限$W$W，求最多带走多少价值的石头。

同样需要观察问题解的结构，让问题能够更小的表示，然后发现问题表示之间的递推关系。

假设有1,…,n这些石头，（1）如果n不在结果S中，那么结果S对于1,…,n-1这些石头来说同样是最优解。
(2）如果n在最终结果S中，那么S-{n}这个解对应的就是1,…,n-1这些石头在背包容量限制为W-w_{n}时候的最优解。

于是这个问题的解的表示与石头和容量两个变量有关：

同样也能发现这样的解之间的关系。于是我们就定义一个更小的问题表示：

接着就得到了解决这个问题的递推解法：

3. Sequence Alignment Optimal Substructure

算法第二部分刚开始的时候就介绍了这个问题，输入是两个字符串，可以向字符串中增添gap字符来让其对齐，找到对齐之后penalty最小的方式。与gap对齐和不同字符对齐有不同的penalty。

动态规划解法最关键的一步是确定subproblem，一般我们观察问题的最优解法的结构来找到线索。比如我们先将问题进行递归解决，然后反向找出需要的subproblem。

对于这个问题，假设最终的对齐方式如下：

可以发现它们两个字符串结尾两个字符的对应方式有三种情况：

可以相对轻易地用归纳法证明这三种情况经过递推以后的结果同样是最优的。因此我们发现这个问题的subproblem就是更小的两个字符串之间的对齐问题。而从更小的解法递推到更大的问题的解法对应的就是上述三种情况，于是我们就得到了算法的解决方案：

当然这样得到的结果A[i,j]表示的同样是最终的penalty，因此还需要一个重建的过程来得到最终的字符串对齐方式：

4. Optimal Binary Search Trees

对于一个键值集合有很多种搜索树，一般来说最好的就是平衡树比如红黑树。因为平衡树能够保证最坏复杂度为$\Theta(logn)$Θ(logn)。但是对于每个键值被查找概率不均匀的情况，直接用平衡树可能不是最优的解法。现在要解的问题就是，对于n个键值，每个键值都有查找概率$p_{i}$pi​，建立起平均查找长度最小的搜索树。

这个问题与哈弗曼编码数有点相似，都是输出一个最小化平均搜索长度的树。但是哈弗曼编码的限制条件是树需要满足前缀码的条件，而这个问题输出是一个查找树。

这个问题第一眼看去感觉可以用贪心法，但是无论是自上而下还是自下而上建树得到的都不会是最优解，比如下面两个反例：

在自上而下建树的时候，我们发现root结点的选择对于整体的结果影响是最大的。但是如果我们知道了root结点的选择，那就能够进行比较。或许可以在动态规划解法中遍历根节点的选择。

同样来观察最优解法的结构。对于最终的解法来说，根节点r的左子树$T_{1}$T1​与右子树$T_{2}$T2​必然也是各自结点表示的最优结构：

反证法证明过程省略。大致就是假设最优解时的左子树可以不是最优解$T_{1}$T1​，然后发现这么算得到的解的加权和大于左子树是$T_{1}$T1​时候的结果得出矛盾。

对于从i开始到j结束这些结点，求这些结点的最优解需要遍历每个结点作为根节点的情况然后做比较得到最优的结果：

根据这个递推就可以写出最终的解法：

可以看出实际上有三重循环，因此复杂度为$O(n^{3})$O(n3)。