这一讲我们介绍一个序列比对的例子。序列比对呢， 它是为了确定两个序列之间的相似性或者同源性， 把它们按照一定的规律排列，进行比对。 那么它的输出就是这两个相似性到底有多大， 我需要经过多少个操作把第一个序列变成到第二个序列，它是通过这样的办法来考虑它的- 相似性。 那么序列比对呢，它有着非常广泛的应用。 比如说在生物学，我们会研究同源性， 比如蛋白质序列或者DNA的序列，在比对中， 我们可以找到它的错配或者突变， 找到它的空位可以表示它的插入或者缺失 等等。所以这些个比对呢可以反映这两个序列之间的 差别，这在生物学研究中是可能用到的信息。还有在 计算语言学中用于表示一个语言进化或者文本相似性的研究，也会 用到序列比对，所以这是一个有着应用背景一个重要的问题。下边我们先看看两个序列 是怎么样比对的。它是通过这个编辑距离，给定了两个序列S1和S2， 可以规定一系列的操作，就是编辑操作，就是对字符进行插入， 或者是删除，或者是替换，这是 最基本的操作，有这样一些操作。把这些操作 一系列的这样的操作顺序执行以后，就开始把第一个 序列变成第二个序列了，就是这样转变。 那么当你采用不同的操作顺序的时候，都可能 把第一个序列转变成第二个序列。我们希望找到的是 最小的这样的编辑操作次数，这样的操作呢 次数它的大小这个数就代表它的编辑距离。 就是说我把第一个序列通过多少次操作， 就是最少的那个操作次数转变成S2，这个就叫做， 这个次数就叫做它的编辑距离。我们来看一个例子， 这是第一个字符串，这是第二个字符串，我们希望把 这个字符串转变成这个字符串，它的编辑距离是多少呢？ 下边先给出一个操作顺序，这个操作顺序通过6步的编辑操作就可以把第一个 字符串转变成第二个字符串。那这只是给出了一种操作的顺序，通过这个操作顺序我们知道 它的编辑距离不会超过6，最多是6步。下边我们看一下这是原始的这个序列， 然后第一个操作呢是删除这个v，把它删除，变成 下边这个序列，这是第一步操作。第二步操作呢，插入w在前边， 这样就变成了这个序列了。 然后插入r，在w后边插入r， 就变成下边这个序列了。然后我们删除n， 把这个n删除掉，变成下边这个序列了。 再删除n，把t后边这个n再删除掉，就变成下边这个序列了。 最后在后边插入一个s，这就得到了这个目标序列，得到了， 由原始的序列变成这个目标序列了。我们中间经过了这样6步的操作， 所以可见至多6步操作就可以完成这个序列的转换，它的编辑距离至多是6。 下边我们看一下这个子问题的界定和归约。假定这是两个序列， 一个是1到n的，一个是1到m的序列，那么它的子问题是什么呢？ 子问题是第一个序列是1到i，取它的一个子部分前半段， 然后第二个序列呢也取它的子部分，是1到j，这样的子部分。 那么这个子问题就由这两个序列的后边界来界定这个子问题， 就是i和j一对这样的参数来界定这个子问题。 那么下边我们看一下这个操作，假定我们现在计算这个子问题， 它在做操作的时候，那么如果把 第一个序列的第i个字符删掉，删掉以后 它就归约成，就是第一个序列从1到i-1，和 第二个序列的编辑操作了，所以就归约成子问题（i-1,j）的 这个边界的子问题。那么你这个删除操作呢，它需要增加1的编辑距离， 这是第一种情况。那么如果 我在S1的这个序列的后边，我插入一个 字符，刚好是第二个序列的最后一个字符，如果进行这样的编辑操作， 那就相当于原来的子问题是S1[1..i] 的这个问题，和第二个序列的1到j的 第二个取一个它的前段，1到j的前段的这样的一个计算问题，它的编辑距离。然后加上- 这个插入 操作以后，就得到了它到它的一个转换。所以这个 编辑的操作加上1，这个是插入操作的这个 工作。那么还有一种是替换，就是 把它的第i个字符替换成第2个序列的第j个字符，这样的 替换的编辑操作，而这个操作它的编辑距离也是1，是一步操作， 它就归约成前边的是1到i-1的，而第二个序列是1到j-1的， 那个子问题的编辑操作，加上一步替换操作，就可以变成 S1到S2的这个编辑了。所以这个就是归约成 前边那个，第一个序列减1，第二个序列减1的这个子问题， 这个操作也是1。如果这个的最后一个字符，第i个字符和第二个序列的第j个 字符是完全相同的字符，这个时候我们需要0个编辑操作就可以了， 就是不要做任何操作，只要是把它的1到i-1的这个序列 变化到第二个的1到j-1个序列，就是这个子问题的编辑操作做完了 就可以了，所以这步操作是0个操作，这是它的归约的方法。 我们把这个归约的方法可以体验到它的递推方程里边去。 那C[i，j]表示的是 第一个序列1到i的序列，第二个序列是1到j的序列，这是目标序列。 把第一个序列变到第二个序列的编辑距离，就是C[i，j]。 那按照刚才的分析呢，它有几种可能的方法。一个是删除，那就是 C[i-1, j]归约成这个子问题的编辑距离加上1， 如果要是插入，那归结成 就是说第一个序列不动，第二个序列减1的这样的一个 编辑距离加上1。那么如果是替换操作和最后 两个字符完全一样，不需要操作，体现在这一项里头。这个是它的子问题， 第一个序列减少一个字符，第二个序列减少一个字符。它是子问题的 编辑距离，加上t[i, j]，t[i, j]就是说 这次的编辑操作的工作量。如果它的第一个序列的最后字符跟第二个序列的最后字符相同的 时候，这个工作量是0。如果是替换操作，第一个字符被替换成第二个序列的这个 字符的时候，它的编辑操作的工作量是1。这就是根据刚才的那个分析得到的递推方程。 它的初值呢，就是当有一个序列变空的时候，它就需要把所有的项都得 加进来，这个时候是需要j的工作量， 这个时候需要i的工作量。这是它的两个初值。 下边看一下它的复杂度的分析， 这个复杂度呢它是由子问题的个数和每个子问题的 工作量来决定。子问题是由i，j两个参数来界定的， 那么这个i和j的最大的值，一个是m，一个是n，所以它有O(m,n)个 子问题，每个子问题的计算呢是常数时间，根据刚才的递推方程已经看到了， 那些子问题的C的值都是可以查到的，经过常数次的操作就可以得到新的这个问题的 优化函数值。所以这么多个子问题每个都是常数时间，最后的工作量就是O(n,m) 就可以了。那么通过这些个动态规划的例子， 我们来总结一下动态规划算法的设计要点。 首先通过参数来界定子问题的边界， 这个边界呢可能是一个参数，也可能是两个参数，同类型的参数 或者不同类型的参数，所以这是考虑的第一个要素。 另外呢，要注意子问题的重叠程度。动态规划算法之所以 比蛮力算法好，效率高，是在于它的每一个子问题只算一次， 如果在动态规划算法里面，它的子问题出现的次数 非常少，前边你存在那，后边几乎不再引用，那你相当于 跟蛮力算法就没有太大的区别了。所以只有子问题被 多次重叠出现，后面计算的时候老要调用这个值，这个时候动态规划算法 才能体现出它的时间效率。这是第一个需要注意的地方。 第二个给出带边界参数的优化函数的定义，你要 说明这个优化函数是什么含义， 另外给出它的递推关系，给出 初值，这是动态规划算法的一个关键。只有 有了这个方程，你在后边实现这个算法的时候，才能 给出相应的计算规则。这是一个关键的地方。 当你列出这个递推方程以后就可以判断它是不是满足优化原则， 不满足优化原则是不能使用动态规划算法的，这是它的必要条件。 考虑要不要标记函数，因为优化函数值 往往是代表着解的一种性能对它的评价，而真正的解 它是需要通过标记函数来追踪的，所以要考虑需不需要设立标记函数。 再下面要 考虑的因为你是迭代计算，自底实现 自底向上的这个实现技术，要从最小的子问题 开始起，所以你要给出一个计算顺序， 就是我们怎么排列，按照子问题的规模从小到大排列，在同样规模的子问题，先算 哪一个后算哪一个，要把这个次序设计好。然后你要迭代 计算，用备忘录来把这个优化函数值和标记 函数值把它存起来，把那个备忘录的表要设计好。 复杂度的估计，这个复杂度的估计呢 它是通过计算备忘录的这个工作量 以及后边追踪解的工作量，两个工作量加起来， 一般情况下，追踪解的工作量比较小。 那么备忘录的工作量怎么估计呢？可以有两种办法， 一种办法我们就直接看一看备忘录有多少个项，每个项 的计算需要多少工作量，全部把它求和。 那么居于每一项的计算，它的工作量怎么看呢？可以通过 递推方程来看一看我计算这个项需要查找哪些个值， 需要遍历什么样的范围等等，来估计每个项的工作量。这是一种方法。 另一种方法就是写出算法的伪码，根据伪码里边的for循环，我们要 进入多少次，在循环体内部，它有多少工作量，这也是 一种估计的方法，两种方法都可以。 最后一个要注意的动态规划算法由于 你是用空间来换时间，它需要存储备忘录这个 空间是比较大的。往往对有一些问题它的规模大的 时候不能使用动态规划算法，是由于这个空间超过了这个计算机的 配置，所以这是它的瓶颈因素。 关于动态规划算法呢，我们可以做下面的总结。 这个动态规划算法它的根本的这些个好处是在于 用空间换时间，每个子问题只计算一次，从而 使得它能够比蛮力算法有更高的效率。关于这个算法呢，我们就介绍到这里。
