专题讲解——动态规划 | Thomas He’s Blog

type

status

date

slug

summary

1. 加权独立集问题 (The Weighted Independent Set Problem）

我们第一个要研究的案例就是加权独立集问题。

假设是一个无向图，那么的独立集是的一个子集，其中顶点互不相邻：对于任意两个顶点。举例来说，如果顶点代表人，边表示两个人互不喜欢，那么独立集对应的就是都能和睦相处的一群人。又或者，顶点代表需要选修的课程，边表示两个课程相互冲突，那么独立集对应的就是一个可行的课程表。

⏰

小测试 5 个顶点的完全图有多少种不同的独立集？

5 个顶点的环呢？

a) 1 和 2 b) 5 和 10 c) 6 和 11 d) 6 和 16

好，现在我们应该熟悉了独立集这个概念，那么接下来就可以讨论加权独立集问题了。

❓

问题：加权独立集（Weighted Independent Set, WIS）输入：无向图，以及每个顶点的权重。 输出：无向图的一个独立集，其中顶点的权重之和最大，也就是使得最大。

事实上，无向图的加权独立集问题至今依然没有通用的、快速的、正确的求解方式（NP-hard）。不过，我们可以挑战一下它的简单情形：路径图的加权独立集问题。

比如，下面这个图：

它有 8 个独立集：空集、四个单顶点集、第一顶点和第三顶点、第一顶点和第四顶点以及第二顶点和第四顶点。路径图独立集的数目与顶点数目呈指数增长（why?），因此，当规模比较大的时候，穷举法是不可行的。

1.1 尝试贪心算法

对于很多问题来说，贪心算法是开始头脑风暴的好地方。即使贪心算法失败了（情况往往是这样orz），它也可以帮助你理解问题的复杂性。

对于 WIS 问题，最自然的贪心算法是这样的：对所有顶点按权重从高到低排序。遍历所有顶点，如果当前顶点与结果集中的所有顶点都不相邻，则将当前顶点加入结果集。伪代码如下：

📌

WIS: 尝试贪心算法 对中的所有顶点，按权重从高到低排序 for 每一个，按权重从高到低的顺序 do if 是图的一个独立集 then return

是不是很简单，但是它能正常工作吗？

⏰

小测试 当输入是上面有 4 个顶点的路径图时，贪心算法输出的结果是多少？它是所有独立集中的最大值吗？ a) 6; 不是 b) 6; 是 c) 8; 不是 d) 8; 是

1.2 动态规划

动态规划的关键在于思考这样一个问题：假如有人把最优解放在了我们面前，那么最优解长什么样子呢？或者说，最优解具有怎样的结构？

以上面的问题为例，表示有 n 个顶点的路径图，是它的 n-1 条边，是顶点的权重。假设我们神奇地知道了图的一个最大加权独立集，它的总权重为。那么长什么样子呢？它具有怎样的结构？

我们可以这么说：要么包含最后一个顶点，要么不包含。

Case 1: 。从中删除最后一个顶点和最后一条边，我们得到图。那么一定也是图的一个最大加权独立集。

Case 2: 。假设包含最后一个顶点，那么它一定不会包含。从中删除最后两个个顶点以及和它们相关联的边，我们得到图。那么一定是图的一个最大加权独立集。

换句话说，我们现在知道长什么样子了（也就是这个问题的最优子结构）。

📌

WIS：最优子结构 假设是路径图的一个最大加权独立集 (MWIS)。令表示由图中前个顶点和前条边组成的子图。那么，只有两种情况： a) 图的一个 MWIS b) 图的一个 MWIS

图的最大加权独立集只可能是上述两种情况中的一种，因此它们中具有更大权重者胜出。

📌

WIS: 递归公式 令表示的 MWIS 的总权重（）。那么，我们有：

更一般地说，对于每一个有

📌

WIS: 子问题子问题是什么：求的最大加权独立集（） 子问题的个数：

Naive 递归实现：

但是递归的实现方式，存在大量的重复计算，性能很低，时间复杂度是指数级别的。我们期望一种更高效的实现方式。

线性时间的动态规划实现：

例如，路径图如下的话：

那么数组最终的值应该是这样的：

但是，上面的算法只是告诉了我们 MWIS 的总权重是多少，并没有告诉我们里面具体包含哪些顶点…

接下来，我们将看到，如何根据已计算的数组重构 MWIS。

如果，那么的 MWIS 就是的最大加权独立集。因此的 MWIS 中不包含顶点。

如果，那么的 MWIS 就是的 MWIS。因此的 MWIS 中包含顶点。

1.3 动态规划的原则

📌

动态规划范式

确定子问题集合 (子问题的数目决定了时间复杂度，因此不能太多)。

展示如何根据"较小"子问题的解，计算"较大"子问题的解 (递归式，又称为状态转移方程)。

展示如何从所有子问题的解中推断出最终解。（后期处理，例如上面的重构过程）

当这三个问题想清楚了，相应的动态规划程序就好写了:从"最小"到"最大"，系统地逐个解决所有的子问题，并从这些子问题的解中计算处最终的解。

1.4 动态规划 VS. 分治

熟悉"分治"算法设计范式的同学可能会发现它与动态规划有一些相似之处。这两种范式都是先解决较小的子问题，并将结果合并为初始问题的解。下面我们罗列一下这两个范式之间的区别（目的是为了让大家更好地理解这两个范式）：

分治算法分解子问题的方式，一般是比较单一的（比如归并排序，和快速排序）。然而，动态规划可以以多种方式分解子问题，然后从这些子问题中选择最优的。

动态规划递归调用的时候，每次都会对多个子问题进行选择。同一个子问题会被重复计算多次，因此我们必须缓存子问题的解。然而在大多数的分治算法中，分解的子问题都是不同的，缓存子问题的解是没有必要的。

在分治算法中，我们往往是根据运行时间来选择如何分解子问题，分治算法的正确性往往是显而易见的。在动态规划中，我们是根据程序的正确性来决定如何分解子问题，而不会考虑程序的运行时间。

正是因为第 3 点，分治算法的子问题往往会缩减地很快，通常是按某个比例（比如：50%）缩减的。而动态规划的子问题往往缩减地很慢（例如：WIS 问题），因为它必须考虑程序的正确性。

分治可以看作是动态规划的一个特例。作为一种更复杂的算法设计范式，动态规划适用于更广的问题，相应地它对技术的要求也更高。

接下来，就通过两个更加难一点的问题，来磨练我们的动态规划技术吧！

2. 背包问题（The Knapsack Problem）

背包问题是这样一个问题：有个物品，分别编号为。每个物品的价值为，大小为。现在我们有一个背包，容量为。问：如何将物品装进背包里面，使得背包里面的物品总价值最大。

❓

问题：背包 输入：n 个物品，它们的价值分别为，大小分别为。以及容量为 C 的背包。输出：物品的一个子集，满足：，且的值最大。

背包问题实际上是一个非常基本的问题。每当你拥有稀缺资源，并希望以最佳的方式加以利用时，你就在讨论一个背包问题。

📌

Knapsack: 最优子结构?

📌

Knapsack: 递归公式（状态转移方程）？

📌

Knapsack: 子问题是什么？有多少个？

c++代码：

例子：背包容量 C = 6

Item	Value	Size
1	3	4
2	2	3
3	4	2
4	4	3

3. 序列对齐（Sequence Alignment）

如果你选修了基因组计算课程，那么前几节课很可能会专门讨论序列对齐问题。在这个问中，输入由两个字符串组成，分别代表基因组的某一部分。两个字符串的长度不必相同，例如：输入可以是 AGGGCT 和 AGGCA 。简单来说，序列比对问题就是在计算这两个字符串的相似度。

我们示例的字符串 AGGGCT 和 AGGCA 显然是不同的，但直观上，它们的相似度更高。那么怎样才能将这种直觉形式化呢？一种方法注意到了这两个字符串可以"很好地对齐"：

这两个字符串在 6 列中有 4 列是相同的；唯一的缺陷是：中间有一个间隙以及最后一列中 A 和 T 是不匹配的。

好了，现在我们可以给“对齐”下一个正式的定义了：一般来说，对齐是在一个或两个输入的字符串中插入间隙，使其等长的一种方法。

❓

问题：序列对齐 输入：字母表中的两个字符串。如果字母表中的两个字符不匹配，则会造成损失；插入一个间隙会造成损失输出：的一个对齐，使得总损失最小。

📌

Sequence Alignment: 最优子结构？

📌

Sequence Alignment: 递归公式（状态转移方程）？

📌

Sequence Alignment: 子问题是什么？有多少个？

C++实现：

归纳总结

参考文献

一些引用

引用文章

💡

欢迎您在底部评论区留言，我们一起交流学习~