写在前面
动态规划针对特定问题求解的例子有很多, 本文将从普适的情况来系统地定义及分析动态规划. 我们首先提出两个问题.
Problem 1.1
给定三个字符串A, B, C, 试求出 A 和 B 的一个满足下述条件的最长公共子序列: 这个子序列不能包含字符串 C 作为它的子序列.
Problem 2.1
试分析动态规划问题的空间复杂度.
第一个问题是一个经典问题"最长公共子序列" (Longest Common Subsequence, LCS) 的一个扩展. 注意子序列 (subsequence) 和子串 (substring) 的区别在于, 子串指原字符串中连续出现的若干字符, 而子序列则不要求在原字符串中出现的字符连续 (保证次序即可). 举个例子, "hlo" 是字符串 "hello" 的子序列而不是子串, 因为它在 "hello" 中不连续.
第二个问题更系统一些. 仅仅用针对特殊动态规划问题的求解模型是回答不清楚这个问题的. 为了把它解释清楚, 我会从半环开始来定义动态规划问题的适用范围, 从而揭示出动态规划问题的本质, 并通过更底层的代数结构来解释动态规划的空间复杂度.
Problem 1.1
给定三个字符串A, B, C, 试求出 A 和 B 的一个满足下述条件的最长公共子序列: 这个子序列不能包含字符串 C 作为它的子序列.
Problem 2.1
试分析动态规划问题的空间复杂度.
第一个问题是一个经典问题"最长公共子序列" (Longest Common Subsequence, LCS) 的一个扩展. 注意子序列 (subsequence) 和子串 (substring) 的区别在于, 子串指原字符串中连续出现的若干字符, 而子序列则不要求在原字符串中出现的字符连续 (保证次序即可). 举个例子, "hlo" 是字符串 "hello" 的子序列而不是子串, 因为它在 "hello" 中不连续.
第二个问题更系统一些. 仅仅用针对特殊动态规划问题的求解模型是回答不清楚这个问题的. 为了把它解释清楚, 我会从半环开始来定义动态规划问题的适用范围, 从而揭示出动态规划问题的本质, 并通过更底层的代数结构来解释动态规划的空间复杂度.
重叠(overlapping)
我们在前文中提到了分治法, 即把母问题转换成子问题来求解的方法. 为了引入动态规划的概念, 我们从一个例子谈起.
Problem 1.0
给定两个字符串 A,B, 试求 A 和 B 的一个最长公共子序列(LCS).
现在我们尝试用分而治之的思想把这个问题化成一个子问题. 假定字符串 A 以字符 x 结尾, x 前面的部分是 A' ; B 以 y 结尾, 其他部分是 B' . 这时我们可以对 x 和 y 分情况讨论. 一方面, 如果 x 与 y 都等于某个字符 "c", 那么我们有一个直观的想法, 就是 A 和 B 的最长公共子序列一定包含字符 "c". 事实上, 如果 A 和 B 的任意一个公共子序列不包含字符 "c", 那么我们把 "c" 加到它的后面, 那么它一定仍是 A 和 B 的最长公共子序列. 换句话说, 这个不包含字符 "c" 的公共子序列一定是 A' 和 B' 的公共子序列. 那么我们就明白, A' 和 B' 的一个最长公共子序列的后面加上 "c", 一定是 A 和 B 的一个最长公共子序列.
另一方面, 如果 x 不等于 y , 那么 x 和 y 一定有一个字符不是它们任意一个公共子序列的最后一个字符. 换言之, 这时 A 和 B' 的公共子序列与 A' 和 B 的公共子序列合并起来, 等于 A 和 B 的公共子序列.
根据上面的分析, 我们如果用 LCS(A, B) 来表示 A 和 B 的最长公共子序列的大小, 就可以写出如下的公式.
Problem 1.0
给定两个字符串 A,B, 试求 A 和 B 的一个最长公共子序列(LCS).
现在我们尝试用分而治之的思想把这个问题化成一个子问题. 假定字符串 A 以字符 x 结尾, x 前面的部分是 A' ; B 以 y 结尾, 其他部分是 B' . 这时我们可以对 x 和 y 分情况讨论. 一方面, 如果 x 与 y 都等于某个字符 "c", 那么我们有一个直观的想法, 就是 A 和 B 的最长公共子序列一定包含字符 "c". 事实上, 如果 A 和 B 的任意一个公共子序列不包含字符 "c", 那么我们把 "c" 加到它的后面, 那么它一定仍是 A 和 B 的最长公共子序列. 换句话说, 这个不包含字符 "c" 的公共子序列一定是 A' 和 B' 的公共子序列. 那么我们就明白, A' 和 B' 的一个最长公共子序列的后面加上 "c", 一定是 A 和 B 的一个最长公共子序列.
另一方面, 如果 x 不等于 y , 那么 x 和 y 一定有一个字符不是它们任意一个公共子序列的最后一个字符. 换言之, 这时 A 和 B' 的公共子序列与 A' 和 B 的公共子序列合并起来, 等于 A 和 B 的公共子序列.
根据上面的分析, 我们如果用 LCS(A, B) 来表示 A 和 B 的最长公共子序列的大小, 就可以写出如下的公式.
$$ LCS(A, B) = \begin{cases} LCS(A', B') + 1 & if \ x = y \\ max\{LCS(A', B) , LCS(A, B')\} & if \ x \neq y \end{cases} $$
注意两点. 第一, A' 和 B' 的长度小于 A 和 B 的长度, 因此我们实际上把母问题转化成了子问题. 第二, 这个子问题和母问题有着很大的重叠(overlapping). 事实上, A 和 B 的所有前缀们的最长公共子序列的求解, 都包含在求 LCS (A, B) 这个母问题的框架内.
注意, A 的子序列的个数是指数级的, 如果通过列举 A 的所有子序列, 查看它们是不是 B 的子序列的方法来求解 LCS 的话, 我们需要指数级的验证次数. 由于指数级的时间代价比任意一个多项式级的时间代价都高, 因此这个算法的复杂度也是指数级的. 而利用这个重叠(overlapping)的话可以优化这个问题.
另一个优化是这样的. 如果我们直接求LCS(A, B), 最坏的情况是我们需要转化成求两个子问题, 而每个子问题可以继续转化成两个子问题; 最终子问题的个数也是指数级的. 为了避免这个情况, 我们决定放弃"从大往小"求LCS的方法, 用另一种方法去充分利用这个重叠(overlapping).
假定 A 和 B 的长度不超过 n . 注意到 A 和 B 只有 O(n) 个前缀, 因而只有 O(n*n) 个最长公共子序列需要求. 而一个前缀的最长公共子序列只依赖长度比它更小的前缀. 也就是说, 如果我们从前缀小的子问题开始求, 后面的问题就可以直接利用前面求好的结果, 根据上面的公式, 用 O(1) 的时间就可以求出一个子问题.
我们给出problem 1.0 的解法.
注意, A 的子序列的个数是指数级的, 如果通过列举 A 的所有子序列, 查看它们是不是 B 的子序列的方法来求解 LCS 的话, 我们需要指数级的验证次数. 由于指数级的时间代价比任意一个多项式级的时间代价都高, 因此这个算法的复杂度也是指数级的. 而利用这个重叠(overlapping)的话可以优化这个问题.
另一个优化是这样的. 如果我们直接求LCS(A, B), 最坏的情况是我们需要转化成求两个子问题, 而每个子问题可以继续转化成两个子问题; 最终子问题的个数也是指数级的. 为了避免这个情况, 我们决定放弃"从大往小"求LCS的方法, 用另一种方法去充分利用这个重叠(overlapping).
假定 A 和 B 的长度不超过 n . 注意到 A 和 B 只有 O(n) 个前缀, 因而只有 O(n*n) 个最长公共子序列需要求. 而一个前缀的最长公共子序列只依赖长度比它更小的前缀. 也就是说, 如果我们从前缀小的子问题开始求, 后面的问题就可以直接利用前面求好的结果, 根据上面的公式, 用 O(1) 的时间就可以求出一个子问题.
我们给出problem 1.0 的解法.
动态规划(Dynamic programming)
Answer 1.0
A 和 B 中有一个是空串的时候, 结果为空串. 否则, 根据上面的公式, 我们总可以通过比较 A 和 B 的最后一个字符, 以及 A 和 B 的前缀来确定 LCS(A, B), 时间是O(1). 我们规定一个步骤 k , 即求出 A 的某个前缀和 B 的某个前缀的最长公共子序列, 其中这两个前缀的长度之和为 k . 假设 A 和 B 的长度是 u 和 v, 那么步骤 u+v 即为所求. 因此, 算法描述如下. 首先, 我们根据空串的分析做步骤 0 ; 其次根据公式来做步骤 1 , 再做步骤 2, ... 直到做完步骤 u+v . 这样, 我们就用了 O (u*v) 的时间, 求出了LCS(A, B).
上面的例子所使用的算法就是动态规划算法. 一般地, 使用分治法把母问题转化成子问题, 而且充分利用子问题之间共同的重叠 (overlapping) 部分的算法, 称为动态规划(Dynamic Programming, DP).
现在我们尝试回答problem 1.1. 我们很容易看出LCS的这一套"动态规划"方法可以用在此问题上面, 现在我们关心的是能否用O(n^2)的时间复杂度来解决这个问题. 考虑LCS的解法, 我们把 A 和 B 的一对前缀的组合称为一个状态. 在LCS这个问题中, 我们本质只是按照某一个特定的顺序, 把所有状态遍历了一遍. 当前我们有O(n^2)个状态, 每一个状态对应 A 和 B 的一个前缀, 以及它们的一个最长公共子序列.
我们尝试在这O(n^2)的状态上都添加一个标签. 假定这个标签代表这个状态上的最长公共子序列和"不得被包含" 的 C 的某一个关系. 一个直接的想法便是我们可以用这个标签记录当前最长公共子序列已经把 C "包含到什么程度"了. 假定一个状态(A', B') 的最长公共子序列为 S, 注意 C 可能有前 t 个字符已经被 S 顺序包含, 我们用 t 来做这个标签.
这样的话, 只要 t 没有达到 C 的长度, 我们就知道当前的最长公共子序列没有包含 C . 而 t 是很好求的, 对于最长公共子序列的递推公式来讲, 我们只需要考虑子序列新添加的字符是不是 C 的第 t+1 个字符就可以了. 如果是的话, 当前的标签递增一次, 只要当前的标签没有达到 C 的长度, 我们就认为这个状态仍然是合法的. 我们尝试把这个想法变成一个解法.
Wrong Answer 1.1
我们在 Answer 1.0 的基础上为每一个状态增加一个标签 t , 代表当前最长公共子串包含的 C 的最大前缀的长度. 这样的话, 递推公式只需要做出一点修改: 当 t 等于 C 的长度减 1 , 而且当前最长公共子序列要增添的一位刚好是 C 的最后一个字符的时候, 我们可以考虑不更新, 或者换一种方式更新, 来保证新的最长公共子序列不包含 C.
解法已经描述完了. 现在我们考虑这样一个例子. A = "abd@@@c", B = "adb@@@c", C = "adc". 这里@所代表的所有的字符都不相同, 而且都不等于abcd中的任何一个. 那么对于(A', B')来说, 会记录到的LCS有可能是 "ab" 或者 "ad". 我们不妨假设它记录了 "ad". 那么, 在求LCS(A, B)的这一个步骤的时候, 我们的 t 发现如果把 "c" 添加进来的话, 公共子序列就包含 C 了. 因此我们只能面对这样一个状况: 子问题的最优解是"ad", 我们遇到了"c", 无法更新. 一个选择是直接把"ad"作为母问题的最优解. 最长公共子序列的长度是2. 可是这个问题的最优解是"abc", 长度为 3 . 本质原因是子问题的最优解和母问题的最优解不存在之前所说的递推关系了.
A 和 B 中有一个是空串的时候, 结果为空串. 否则, 根据上面的公式, 我们总可以通过比较 A 和 B 的最后一个字符, 以及 A 和 B 的前缀来确定 LCS(A, B), 时间是O(1). 我们规定一个步骤 k , 即求出 A 的某个前缀和 B 的某个前缀的最长公共子序列, 其中这两个前缀的长度之和为 k . 假设 A 和 B 的长度是 u 和 v, 那么步骤 u+v 即为所求. 因此, 算法描述如下. 首先, 我们根据空串的分析做步骤 0 ; 其次根据公式来做步骤 1 , 再做步骤 2, ... 直到做完步骤 u+v . 这样, 我们就用了 O (u*v) 的时间, 求出了LCS(A, B).
上面的例子所使用的算法就是动态规划算法. 一般地, 使用分治法把母问题转化成子问题, 而且充分利用子问题之间共同的重叠 (overlapping) 部分的算法, 称为动态规划(Dynamic Programming, DP).
现在我们尝试回答problem 1.1. 我们很容易看出LCS的这一套"动态规划"方法可以用在此问题上面, 现在我们关心的是能否用O(n^2)的时间复杂度来解决这个问题. 考虑LCS的解法, 我们把 A 和 B 的一对前缀的组合称为一个状态. 在LCS这个问题中, 我们本质只是按照某一个特定的顺序, 把所有状态遍历了一遍. 当前我们有O(n^2)个状态, 每一个状态对应 A 和 B 的一个前缀, 以及它们的一个最长公共子序列.
我们尝试在这O(n^2)的状态上都添加一个标签. 假定这个标签代表这个状态上的最长公共子序列和"不得被包含" 的 C 的某一个关系. 一个直接的想法便是我们可以用这个标签记录当前最长公共子序列已经把 C "包含到什么程度"了. 假定一个状态(A', B') 的最长公共子序列为 S, 注意 C 可能有前 t 个字符已经被 S 顺序包含, 我们用 t 来做这个标签.
这样的话, 只要 t 没有达到 C 的长度, 我们就知道当前的最长公共子序列没有包含 C . 而 t 是很好求的, 对于最长公共子序列的递推公式来讲, 我们只需要考虑子序列新添加的字符是不是 C 的第 t+1 个字符就可以了. 如果是的话, 当前的标签递增一次, 只要当前的标签没有达到 C 的长度, 我们就认为这个状态仍然是合法的. 我们尝试把这个想法变成一个解法.
Wrong Answer 1.1
我们在 Answer 1.0 的基础上为每一个状态增加一个标签 t , 代表当前最长公共子串包含的 C 的最大前缀的长度. 这样的话, 递推公式只需要做出一点修改: 当 t 等于 C 的长度减 1 , 而且当前最长公共子序列要增添的一位刚好是 C 的最后一个字符的时候, 我们可以考虑不更新, 或者换一种方式更新, 来保证新的最长公共子序列不包含 C.
解法已经描述完了. 现在我们考虑这样一个例子. A = "abd@@@c", B = "adb@@@c", C = "adc". 这里@所代表的所有的字符都不相同, 而且都不等于abcd中的任何一个. 那么对于(A', B')来说, 会记录到的LCS有可能是 "ab" 或者 "ad". 我们不妨假设它记录了 "ad". 那么, 在求LCS(A, B)的这一个步骤的时候, 我们的 t 发现如果把 "c" 添加进来的话, 公共子序列就包含 C 了. 因此我们只能面对这样一个状况: 子问题的最优解是"ad", 我们遇到了"c", 无法更新. 一个选择是直接把"ad"作为母问题的最优解. 最长公共子序列的长度是2. 可是这个问题的最优解是"abc", 长度为 3 . 本质原因是子问题的最优解和母问题的最优解不存在之前所说的递推关系了.
那么, 子问题是否可以记录"ab"和"ad"两个序列呢? 答案是否定的.
假设A = "awxyz@@@c", B = "azyxw@@@c", 那么我们子问题的全部最优解的有四个, "aw", "ax", "ay", "az". 事实上, 子问题的全部最优解是指数级的. 我们不能在一个多项式时间内简单地把子问题所有的最优解压进一个状态下.
为什么当前的解法不能在O(n^2)个状态内解决这个问题? 事实上, 动态规划有一个单调性的保证在里面. 拿LCS这个问题本身来举例, 如果 x 不等于 y, 那么子问题的全部最长公共子序列的长度都无法增加; 如果 x 等于 y , 那么子问题的全部最长公共子序列的长度都只能加一. 我们选定了一个最长公共子序列, 它在进行状态转移之后仍然是最长的公共子序列. 换言之, 这个LCS在状态转移的前后, 单调性不发生改变. 我们刚刚的错误解法的本质原因是在状态转移的过程中改变了单调性.
我们需要更深入地理解动态规划. 暂时而言, 我们的单调性分析局限于具体的例子. 而动态规划本身可以需要被更广泛地把单调性定义出来, 从而可以用这个单调性分析所有的问题, 从而知道哪些建模方法适用动态规划, 哪些建模方法不适用.
我们所使用的定义动态规划中模型的代数结构叫做半环(semiring). 一般地, 一切适用于动态规划的模型, 都是半环或其扩展. 把动态规划用代数结构去解读一下之后, 我们便可以透析它的本质, 从而彻底解决"哪些模型适用于动态规划, 哪些模型不适用"这个问题.
我们需要更深入地理解动态规划. 暂时而言, 我们的单调性分析局限于具体的例子. 而动态规划本身可以需要被更广泛地把单调性定义出来, 从而可以用这个单调性分析所有的问题, 从而知道哪些建模方法适用动态规划, 哪些建模方法不适用.
我们所使用的定义动态规划中模型的代数结构叫做半环(semiring). 一般地, 一切适用于动态规划的模型, 都是半环或其扩展. 把动态规划用代数结构去解读一下之后, 我们便可以透析它的本质, 从而彻底解决"哪些模型适用于动态规划, 哪些模型不适用"这个问题.
很多学者尝试对动态规划问题进行系统化的总结, 其中做的最好的一篇文章是黄亮作为独立作者发表的一篇教程(tutorial), <Advanced Dynamic Programming in Semiring and Hypergraph Frameworks>, 有兴趣的读者不妨借鉴一下.
黄亮作为算法黑书(算法艺术与信息学竞赛)的作者之一, 14岁时便作为初三学生, 参加由高中生为主体的NOI'96(全国青少年信息学奥赛)并取得了全国第19名的成绩而保送进入上海交大. 这篇文章的原版是他在2006年于宾夕法尼亚大学攻读博士期间创作的. 经几版修改之后, 被他于08年和09年在两次国际会议中作为tutorial发表.
半环(semiring)
我们首先从幺半群(monoid)定义半环. 虽然这几个名词看起来比较高端, 但总体而言这些理论有很多典型的例子, 了解这些例子的话, 理论是不难理解的.
幺半群(monoid), 是一个带有二元运算的集合. 它带有结合律和单位元两条性质. 这里, 一个集合上的二元运算带有封闭性. 一个封闭二元运算的集合, 其中运算满足结合律并且含有单位元, 则为幺半群.
半环(semiring) 是一个带有两种二元运算的集合. 集合对于第一个二元运算是可交换幺半群(阿贝尔幺半群), 集合对于第二个运算是幺半群. 为了方便说明, 我们不妨把第一个运算记为 + , 单位元记为 0 ; 第二个运算记为 * , 单位元记为 1 .
幺半群(monoid), 是一个带有二元运算的集合. 它带有结合律和单位元两条性质. 这里, 一个集合上的二元运算带有封闭性. 一个封闭二元运算的集合, 其中运算满足结合律并且含有单位元, 则为幺半群.
半环(semiring) 是一个带有两种二元运算的集合. 集合对于第一个二元运算是可交换幺半群(阿贝尔幺半群), 集合对于第二个运算是幺半群. 为了方便说明, 我们不妨把第一个运算记为 + , 单位元记为 0 ; 第二个运算记为 * , 单位元记为 1 .
自然数集合是加法和乘法的半群(注意, 在自然数中加法和乘法都是有交换律的), 全体整数的集合则是加法的群和乘法的半群, 便是一个环(ring). 我们这里虽然借用了整数上的运算符号, 但是半环(semiring)和整数上的环(ring)是有本质区别的.
那么, 对于半环来说, 所谓 + 的可交换幺半群即为 + 满足交换律和结合律, 而且有单位元; * 的幺半群即为 * 满足结合律, 而且有单位元. 此外, 我们需要再定义* 对 + 满足分配律. 在代数结构中, 根据上述性质我们可以额外推导出, 0 可以作为 * 的化子(零元, annihilator).
我们在前文提到过, 动态规划需要有单调性保证. 这里, 单调性中的序关系是用 + 来定义的. 事实上, 一个更弱的条件就可以推导出半环中元素的序关系, 我们在这里介绍幂等(idempotent)半环.
如果一个半环是幂等(idempotent)的, 那么对任何元素 a , 都有 a + a = a. 在幂等半环中我们称 a + b = a 当且仅当 a <= b. 幂等半环有一个理论, 就是这样定义出来的序关系一定是偏序关系(partial order).
这个定义其实是偏序关系的定义(非严格偏序关系). 事实上, 如果对任何 a 都有 a + a 不等于 a , 那么我们就定义了严格偏序关系 < .
进一步讲, 幂等半环(一定存在偏序关系)中的偏序关系如果是全序的, 我们称之为全序幂等半环.
我们在前文提到过, 动态规划需要有单调性保证. 这里, 单调性中的序关系是用 + 来定义的. 事实上, 一个更弱的条件就可以推导出半环中元素的序关系, 我们在这里介绍幂等(idempotent)半环.
如果一个半环是幂等(idempotent)的, 那么对任何元素 a , 都有 a + a = a. 在幂等半环中我们称 a + b = a 当且仅当 a <= b. 幂等半环有一个理论, 就是这样定义出来的序关系一定是偏序关系(partial order).
这个定义其实是偏序关系的定义(非严格偏序关系). 事实上, 如果对任何 a 都有 a + a 不等于 a , 那么我们就定义了严格偏序关系 < .
进一步讲, 幂等半环(一定存在偏序关系)中的偏序关系如果是全序的, 我们称之为全序幂等半环.
这里提一下偏序关系(partial order)和全序关系(total order).
偏序关系和全序关系的区别在于,全序关系中所有的元素两两都可以比大小, 换句话说, 所有的元素都分布在一条直线上, 左边的一定比右边的小, 比如数轴上的大小关系.
而偏序关系则是一种拓扑结构(偏序拓扑). 我们可以把偏序关系中的元素想象成平面上的一些点. 这些点中间有一些箭头, a 指向了 b 说明 a 小于 b. 这个图中所有的箭头都是往右指的, 只是斜率不一样. 而两个点之间有路径才能比较大小. 这样, 一个拓扑结构就呈现出来了.
例如, a -> b, a -> c 这三个点两个箭头构成一个偏序关系. 但是 b 和 c 不能比较大小.
事实上, 不管是幂等半环(无论偏序还是全序)一定存在单调性, 即对于任意的元素a, b, c, 如果a <= b, 那么一定有 a * c <= b * c, 而且 c * a <= c * b. 注意 * 没有交换律, 所以必须定义两种情况. 在动态规划的实际模型中, 全序的情况比偏序的情况普遍一些, 而且很多偏序关系往往是从全序关系出发的, 因此很多人忽略了偏序关系的存在 (而诸如动态规划空间复杂度分析这种问题, 是必须从偏序关系入手的) .
幂等半环是动态规划问题可适用的充分条件.
幂等半环是动态规划问题可适用的充分条件.
深入地讲, 通过实数半环的Viterbi算法我们可以看出, 一类非幂等半环是可以进行动态规划的. 事实上, 动态规划问题的可适用范围可以推广到更大的范围中. 我会在另一篇文章中提到动态规划适用性的一个更强的充分条件.
对于一类最大, 最小值问题,我们只能限定在幂等半环的模型上做, 单调性分析也是在幂等半环上进行的, 例如我们的problem 1.1.
对于半环上的动态规划来说, 定义域上可能不存在偏序关系, 但是状态空间上一定是有偏序关系的. 我们可以用Viterbi做假设. 我们规定的状态空间上依照它的迭代深度严格满足一个偏序关系. 当然, 仅在幂等半环上(定义域和解空间都有偏序关系), 我们可以使得两个偏序关系相对应.
感谢wk大牛的提示.
反向有界性(negative boundedness)
用半环定义的动态规划理论中, 有一类很特殊的幂等半环, 叫做优(posterior)幂等半环. 事实上, 在任意一个幂等半环上都可以做动态规划, 优半环不是必须的. 但由于优半环问题涉及的动态规划算法都非常重要, 所以这里需要单独讲讲. 优半环上最著名的一个例子, 是非负权图的最短路径(shortest path)问题.
一个幂等半环称之为优的, 如果对于任意的元素a, b, 都有 a <= a * b, b <= a * b. 换句话说, 两个元素组合起来一定比一个元素差. 非负权图上的最短路径就满足这个性质: 两条边的长度之和相比于它们中的一条边一定会增加, 路径一定会变得越来越长, 而你的目标却是最短. 我们可以简单地把优幂等半环理解为"事情总是会变得越来越差".
优幂等半环有一个非常重要的性质, 即对于所有元素 a , 1 <= a <= 0. 第一个不等号是因为"事情变得越来越差", 第二个不等号是因为 0 是乘法的化子, 所以在优幂等半环中总是最差的.
在优幂等半环中, 我们总可以取到一个比0还要差的结果, 然后用它做为初始值来做优化. 这个又称之为反向有界性(negative boundedness).
一个幂等半环称之为优的, 如果对于任意的元素a, b, 都有 a <= a * b, b <= a * b. 换句话说, 两个元素组合起来一定比一个元素差. 非负权图上的最短路径就满足这个性质: 两条边的长度之和相比于它们中的一条边一定会增加, 路径一定会变得越来越长, 而你的目标却是最短. 我们可以简单地把优幂等半环理解为"事情总是会变得越来越差".
优幂等半环有一个非常重要的性质, 即对于所有元素 a , 1 <= a <= 0. 第一个不等号是因为"事情变得越来越差", 第二个不等号是因为 0 是乘法的化子, 所以在优幂等半环中总是最差的.
在优幂等半环中, 我们总可以取到一个比0还要差的结果, 然后用它做为初始值来做优化. 这个又称之为反向有界性(negative boundedness).
最小生成树(minimum spanning tree)
在这里我们只是拿最小生成树举一个例子, 以启发我们对problem2.1的解答.
我们用半环理论定义了动态规划的问题模型, 而下面这个例子涉及到动态规划的实现方法. 通常来讲, 一个问题模型定义好之后, 实现它的方法有很多.
对于无向非负权图的最小生成树问题来讲, 我们可以有很多不同的算法来求最优解. 比如 Prim 算法, 再如 Kruskal 算法. 那么, 这些算法在底层有什么区别呢?
事实上, 尽管我们所要求的最优解可能是同一个状态(当然也可能有很多状态都达到最优解而我们只求其中一个), 我们在求最优解的顺序是不同的, 而局部最优达到全局最优这个过程中, 产生的拓扑结构也是不一样的.
Prim 算法中, 最小生成树添加点的顺序假如是 A1, A2, A3... An, 那么我们从局部最优达到全局最优的拓扑结构是一个线性结构. 每一步我们都是把一个点添加到我们的局部最优解的集合中, 而同一时间局部最优的状态只有一个.
而 Kruskal 算法则不同. Kruskal 算法的局部最优解拓扑结构是一个典型的树形结构, 尽管这个树和最小生成树没有什么结构上的关系. 一开始我们在不断地扩充局部最优的状态, 之后我们会不断地合并这些状态(合二为一), 直到局部最优的状态只剩下一个的时候, 我们即判定其为全局最优.
下面我们思考一下最小生成树模型的几个问题. 这两种算法的时间复杂度和空间复杂度是多少? 时间复杂度和我们拓扑建图的过程有什么关系? 空间复杂度和我们所分析的拓扑结构有什么关系?
我们用半环理论定义了动态规划的问题模型, 而下面这个例子涉及到动态规划的实现方法. 通常来讲, 一个问题模型定义好之后, 实现它的方法有很多.
对于无向非负权图的最小生成树问题来讲, 我们可以有很多不同的算法来求最优解. 比如 Prim 算法, 再如 Kruskal 算法. 那么, 这些算法在底层有什么区别呢?
事实上, 尽管我们所要求的最优解可能是同一个状态(当然也可能有很多状态都达到最优解而我们只求其中一个), 我们在求最优解的顺序是不同的, 而局部最优达到全局最优这个过程中, 产生的拓扑结构也是不一样的.
Prim 算法中, 最小生成树添加点的顺序假如是 A1, A2, A3... An, 那么我们从局部最优达到全局最优的拓扑结构是一个线性结构. 每一步我们都是把一个点添加到我们的局部最优解的集合中, 而同一时间局部最优的状态只有一个.
而 Kruskal 算法则不同. Kruskal 算法的局部最优解拓扑结构是一个典型的树形结构, 尽管这个树和最小生成树没有什么结构上的关系. 一开始我们在不断地扩充局部最优的状态, 之后我们会不断地合并这些状态(合二为一), 直到局部最优的状态只剩下一个的时候, 我们即判定其为全局最优.
下面我们思考一下最小生成树模型的几个问题. 这两种算法的时间复杂度和空间复杂度是多少? 时间复杂度和我们拓扑建图的过程有什么关系? 空间复杂度和我们所分析的拓扑结构有什么关系?
合并(MERGE)
我们将继续分析动态规划求解中的拓扑结构, 以回答problem 1.1 和 problem 2.1所提出的问题.
首先, 我在前面提到, 很多情况下偏序关系是从全序关系出发的. 事实上, 如果我们把半环中的元素所在的维度拓展开来看, 就可以明白. 如果这个集合在一个维度上是全序关系, 另一个维度上也是全序关系, 那么从两个维度来重新定义的话, 它满足偏序关系.
我们举个例子来说明在两个满足全序关系的维度上重新定义半环模型. 可以把一个全序关系想象成一个数轴表示, 那么在两个维度定义的话相当于取了一个平面坐标系, 以前的大小关系变成了这个二维空间里面的边, 由一个节点指向另一个节点.
偏序关系的维度拓展得到的结果也是一个偏序关系. 总之, 在维度拓展之前和之后, 我们都可以把它看做拓扑结构来考虑.
应该了解到, 动态规划算法中最重要的一部分是状态合并(merge), 事实上, 状态合并的过程既可以在维度拓展之前做, 也可以在之后做. 原因很简单. 我们一直保证了偏序关系, 换句话说就是状态合并前后保证了单调性.
首先, 我在前面提到, 很多情况下偏序关系是从全序关系出发的. 事实上, 如果我们把半环中的元素所在的维度拓展开来看, 就可以明白. 如果这个集合在一个维度上是全序关系, 另一个维度上也是全序关系, 那么从两个维度来重新定义的话, 它满足偏序关系.
我们举个例子来说明在两个满足全序关系的维度上重新定义半环模型. 可以把一个全序关系想象成一个数轴表示, 那么在两个维度定义的话相当于取了一个平面坐标系, 以前的大小关系变成了这个二维空间里面的边, 由一个节点指向另一个节点.
偏序关系的维度拓展得到的结果也是一个偏序关系. 总之, 在维度拓展之前和之后, 我们都可以把它看做拓扑结构来考虑.
应该了解到, 动态规划算法中最重要的一部分是状态合并(merge), 事实上, 状态合并的过程既可以在维度拓展之前做, 也可以在之后做. 原因很简单. 我们一直保证了偏序关系, 换句话说就是状态合并前后保证了单调性.
"动态规划算法中最重要的部分是合并(merge). " 事实上, 状态合并前后保证单调性非常重要, 也是我们在合并的过程中容易忽略的一个地方.
我们在分析很多模型的时候, 往往是根据一些惯例, 或者其它动态规划问题上的算法出发, 去思考合并状态的方法. 而很多错误的成因, 就是因为合并了状态之后破坏了单调性, 从而得到了一个"错误的合并". 事实上, 了解了动态规划这个模型的本质之后就会发现, 从单调性出发去合并状态才是正确的选择.
通过这一点我们指出一下之前对problem 1.1 的错误解法错在哪里.
对于problem 1.1, 初始的状态空间是指数级. 我们在LCS问题上把它合并到了O(n^2)的状态个数. 现在需要考虑新的字符串 C, 因此不加任何优化的话, 由于 C 的存在, 我们的状态空间又拓展到了指数级别. 我们鲁莽地进行了一个很强的合并.
对于一个子问题中的LCS 和 C, 我们应该注意到第一个 LCS 是经过合并之后的一个状态, 这里必须考虑之前合并掉的状态(指数级数量)是否仍然在这个点上保有单调性. 现在 C 是一个包含 n 个前缀(子问题)的字符串(母问题), 我们两个维度同时考虑的话, 总的状态空间其实是一个指数级的数乘以一个线性的数.
现在我们搞清楚了这两个拓扑结构相乘时的情况. 之后我们考虑单调性. 根据我们错误解法的反例, 我们可以知道, 在 C 的这个维度上拓展之后, 单调性不能用一个状态 (零维) 来表示 : 它随 C 的字符分布的不同, 而需要选取不同的状态来代表当前情况下的整个状态空间. 因此O(1)是解决不了这个问题的.
换言之, 我们证明了基于"最长公共子序列", 不存在一种O(n^2)的方法来解决problem 1.1.
那么可不可以用O(n)的空间来保存当前的最优解呢? 我们假定在LCS(A', B') 这个状态的基础上, 多了另一个维度 C' , C' 代表 C 的一个前缀. 现在我们正向地分析, 假定A', B', C'的长度是在扩大的情况下, 观察一下可能出现的情况. 我们把新扩展的三个字符记做 a, b, c.
这个问题是反向有界的( 0 就是LCS的下界), 因此我们可以把每一个状态赋初值 0 , 每次更新的时候考虑新的状态和 self 哪一个大.
如果 a 不等于 b, 我们不需要做任何更新. LCS_wo_subseq(A', B', C') = max(self, state_before). 如果 a 等于 b 但是不等于 c , 我们不需要考虑字符串 C' ,因此更新的方法和前面的一样. 假定A' 的前缀是A'-1, B'类似, 那么, LCS_wo_subseq(A', B', C') = max(self, LCS_wo_subseq(A'-1, B'-1, C')+1 )
前面两种情况和LCS一样. 现在假定a, b, c 完全相等. 我们既需要更新LCS, 又不能在当前的状态下更新(A', B', C'), 因为C'现在完全被LCS(A', B')接受了. 事实上, 这里用了一个很小的办法, 也是动态规划中经常用到的, 就是在当前循环中更新下一重循环的状态. 这里, 我们的 C' 被 LCS(A', B') 所接受了, 但是 C'+1 (C'向后拓展一位) 则差一位没有被接受. 因此我们可以做这样的更新, LCS_wo_subseq(A', B', C'+1) = max(self, LCS_wo_subseq(A', B', C')+1 ). 这样的话, 我们既更新了当前的最大值, 又保证了新的状态中"不被接受性"的成立.
其实我们已经得到动态规划的方法了. 我们现在详细定义一下 LCS_wo_subseq 代表的意思, 就可以做出解答了. 其实每一个 LCS_wo_subseq(A', B', C')的定义只需要做一点点强化, 即 LCS(A', B') "恰好" 没有接受 C' . 所谓恰好, 就是说它接受了 C'-1.
对于一个子问题中的LCS 和 C, 我们应该注意到第一个 LCS 是经过合并之后的一个状态, 这里必须考虑之前合并掉的状态(指数级数量)是否仍然在这个点上保有单调性. 现在 C 是一个包含 n 个前缀(子问题)的字符串(母问题), 我们两个维度同时考虑的话, 总的状态空间其实是一个指数级的数乘以一个线性的数.
现在我们搞清楚了这两个拓扑结构相乘时的情况. 之后我们考虑单调性. 根据我们错误解法的反例, 我们可以知道, 在 C 的这个维度上拓展之后, 单调性不能用一个状态 (零维) 来表示 : 它随 C 的字符分布的不同, 而需要选取不同的状态来代表当前情况下的整个状态空间. 因此O(1)是解决不了这个问题的.
换言之, 我们证明了基于"最长公共子序列", 不存在一种O(n^2)的方法来解决problem 1.1.
那么可不可以用O(n)的空间来保存当前的最优解呢? 我们假定在LCS(A', B') 这个状态的基础上, 多了另一个维度 C' , C' 代表 C 的一个前缀. 现在我们正向地分析, 假定A', B', C'的长度是在扩大的情况下, 观察一下可能出现的情况. 我们把新扩展的三个字符记做 a, b, c.
这个问题是反向有界的( 0 就是LCS的下界), 因此我们可以把每一个状态赋初值 0 , 每次更新的时候考虑新的状态和 self 哪一个大.
如果 a 不等于 b, 我们不需要做任何更新. LCS_wo_subseq(A', B', C') = max(self, state_before). 如果 a 等于 b 但是不等于 c , 我们不需要考虑字符串 C' ,因此更新的方法和前面的一样. 假定A' 的前缀是A'-1, B'类似, 那么, LCS_wo_subseq(A', B', C') = max(self, LCS_wo_subseq(A'-1, B'-1, C')+1 )
前面两种情况和LCS一样. 现在假定a, b, c 完全相等. 我们既需要更新LCS, 又不能在当前的状态下更新(A', B', C'), 因为C'现在完全被LCS(A', B')接受了. 事实上, 这里用了一个很小的办法, 也是动态规划中经常用到的, 就是在当前循环中更新下一重循环的状态. 这里, 我们的 C' 被 LCS(A', B') 所接受了, 但是 C'+1 (C'向后拓展一位) 则差一位没有被接受. 因此我们可以做这样的更新, LCS_wo_subseq(A', B', C'+1) = max(self, LCS_wo_subseq(A', B', C')+1 ). 这样的话, 我们既更新了当前的最大值, 又保证了新的状态中"不被接受性"的成立.
其实我们已经得到动态规划的方法了. 我们现在详细定义一下 LCS_wo_subseq 代表的意思, 就可以做出解答了. 其实每一个 LCS_wo_subseq(A', B', C')的定义只需要做一点点强化, 即 LCS(A', B') "恰好" 没有接受 C' . 所谓恰好, 就是说它接受了 C'-1.
这样的话我们完全在这个维度拓展的点把指数级的状态分开了, 而且由于每一个状态都代表"恰好不能接受"C的一个前缀, 刚好每一个合并前的状态都落到了唯一的新的状态里. 而且这样做的话一个新的状态下每一个LCS都接收了同等长度的C的前缀, 这样的话单调性依然可以得到保持.
Answer 1.1
首先, 我们已证明, 基于LCS不存在一种O(n^2)的解法.
现在定义LCS_wo_subseq(i, j, k): 它表示A[0..i]和B[0..j]的最长公共子序列, 这个序列包含了C[0..k-1]这个子序列, 但却不包含C[0..k]这个子序列. 状态转移方程如下. 其中o[i,j,k] 代表LCS_wo_subseq(i, j, k), l_a, l_b, l_c 分别指向 A, B, C 的最后一个字符.
首先, 我们已证明, 基于LCS不存在一种O(n^2)的解法.
现在定义LCS_wo_subseq(i, j, k): 它表示A[0..i]和B[0..j]的最长公共子序列, 这个序列包含了C[0..k-1]这个子序列, 但却不包含C[0..k]这个子序列. 状态转移方程如下. 其中o[i,j,k] 代表LCS_wo_subseq(i, j, k), l_a, l_b, l_c 分别指向 A, B, C 的最后一个字符.
$$ for\ i, j, k, \begin{cases} o[i,j,k] = max(self, o[i - 1, j, k], o[i, j-1, k]) \\ (if\ A[i] \neq B[j]) \\ o[i,j,k] = max(self, o[i-1,j-1,k]+1) \\ (if\ A[i] = B[j] \neq C[k]) \\ o[i, j, k+1] = max(self, o[i-1,j-1,k]+1) \\ (if\ A[i] = B[j] = C[k]) \\ \end{cases} $$ $$ for\ k = 0..l_c, \\ result = max(o[l_a][l_b][k]) $$
这个算法的时间复杂度是O(n^3).
注意最后我们求出了A和B的LCS "恰好包含" C 中的每一个前缀的情况, 我们要把这些情况全部合起来, 才等于最后的结果. 其实可以看出, o[l_a, l_b, 0] 就是LCS(a, b), 因为 C 没有对它做任何的约束.
另外有一点, 虽然我们的 k 只遍历了 C 的每一个前缀, 但实际上 k 这个维度要多出来一行值, 因为我们在 k 等于l_c的时候实际上已经更新了l_c+1. 那么, o[l_a, l_b, l_c+1]代表什么?
Problem 1.2
给定三个字符串A, B, C, 试求出 A 和 B 的一个满足下述条件的最长公共子序列: 这个子序列需要包含字符串 C 作为它的子序列.
Answer 1.2
首先, 基于LCS不存在一种O(n^2)的解法.
其次, 在 answer1.1 中 o[l_a, l_b, l_c+1] 存的就是这个问题的解.
注意最后我们求出了A和B的LCS "恰好包含" C 中的每一个前缀的情况, 我们要把这些情况全部合起来, 才等于最后的结果. 其实可以看出, o[l_a, l_b, 0] 就是LCS(a, b), 因为 C 没有对它做任何的约束.
另外有一点, 虽然我们的 k 只遍历了 C 的每一个前缀, 但实际上 k 这个维度要多出来一行值, 因为我们在 k 等于l_c的时候实际上已经更新了l_c+1. 那么, o[l_a, l_b, l_c+1]代表什么?
Problem 1.2
给定三个字符串A, B, C, 试求出 A 和 B 的一个满足下述条件的最长公共子序列: 这个子序列需要包含字符串 C 作为它的子序列.
Answer 1.2
首先, 基于LCS不存在一种O(n^2)的解法.
其次, 在 answer1.1 中 o[l_a, l_b, l_c+1] 存的就是这个问题的解.
事实上, 我们在 Prim 算法中, 压缩后的状态空间的结构是一个具有拓扑顺序的图, 而在 Kruskal 以及 LCS, LCS_wo_subseq中, 状态空间的结构是一个超图.
超图是图的一个扩展, 它允许一条边有很多个初始节点. 例如, 在LCS中, LCS(A, B'), LCS(A', B) 和 LCS(A', B') 同时决定了LCS(A,B), 因此它是一个三个点指向一个点的边结构.
拓扑结构(topological structure)
在上面的合并(merge)中, 我们已经讲了拓扑结构的很多内容. 其中, 通过拓扑结构的维度拓展却需要单调性保持来分析状态合并方法, 是整个这套理论的精髓.
下面我们谈一谈 problem 2.1, 也就是动态规划问题空间复杂度分析. 我们先把 Prim 算法和 Kruskal 算法继续分析一下.
下面我们谈一谈 problem 2.1, 也就是动态规划问题空间复杂度分析. 我们先把 Prim 算法和 Kruskal 算法继续分析一下.
分析空间复杂度一般是要去掉输入所占的空间的. 因为从图灵机理论来讲, 输入的纸带(input tape) 给定之后其实你并不需要开额外的空间来存储它, 你只需要移动指针来反复扫这个纸带.
但是保存结果所用的空间却要算在空间复杂度里面. 因为输出纸带(output tape) 是由算法本身来打孔的.
Prim 的空间复杂度比较简单, 只需要有存一个状态的空间就可以完成所有的事情. 因为你每进入一个新的状态, 都可以把原来状态的内容替换掉. 事实上, 原来的状态已经不会再通过转移方程被其它状态所利用了. 因此, 假定图中有 n 个点, 一个状态所花的空间是 s , Prim 的空间复杂度是s, s = O(n).
Kruskal 则作为树形结构存储状态, 最多的时候可能有O(n)个状态. 在最小生成树这个模型里面有一个地方比较巧, 就是这 O(n) 个状态里面的点不会重复, 所以所有状态加起来只需要O(n)的空间. 注意, 这个空间复杂度, 也是在新状态替换掉原来状态达成的. Kruskal 的空间复杂度是 O(n)*s, 其中 O(n)*s = O(n).
再考虑最长公共子序列(LCS). answer 1.1 中我们谈到, 每次只需要求两个子串长度和是 k 的所有状态(步骤 k ). 事实上, 我们在求步骤 k 的时候, 需要用到的当前状态只有第 k-1 步和第 k-2 步, 因此我们只需要同时保存两个连续步骤的所有空间就可以了. LCS 的空间复杂度是O(n).
一个很直观的问题就是, 是不是所有动态规划问题, 都可以在中间过程中把先前状态删掉, 从而省下空间代价呢?
答案是肯定的. 考虑状态空间的拓扑结构, 只要从源点 s 到汇点 t 的任意一条路径上, 仅保留所有状态里面已经遍历的"最后一个"状态, 就可以保证留下剩下的遍历需要所有的空间了. 事实上, "最后一个"是拓扑定义的结果, 假设一个路径上有前 k 个状态被遍历, 后面则没有 (因为遍历的顺序是拓扑顺序, 因此遍历的状态前面不存在未遍历的状态), 我们剩下的遍历只需要最后一个当前已经被遍历的状态.
我们还剩下一个细节没有处理. 注意, 在动态规划问题中, 不仅合并(merge)是由算法架构定义的, 状态的遍历顺序也是. 那么, 我们能否找到一个最"好"的状态遍历顺序, 使得我们从遍历开始到遍历结束所需要的空间代价最低呢? 我们考虑从源点 s 到汇点 t 的任意一条路径上至少需要有一个状态, 这种情况下所有状态所需空间的最小值.
我们尝试用分割的观点来"想象"一下, 一个解的集合是一个什么样的结构. 事实上, 对于任意一个拓扑结构 T 和任意一个给定方向的向量 u , 都可以把它映射到一个二维的图上, 使得所有的状态转移向量(箭头)和 u 的夹角小于90度. 换言之, 任意一个 T 中的向量 v 都满足 u*v > 0. 现在我们需要找到一个最小的状态的集合, 使得它可以割开从源点到汇点的所有路径.
为了直观, 我们把 u 想象成 x 轴, 把二维空间想象成平面直角坐标系. 注意到, 给定任意 T 和 x 轴的方向 , 在满足上述条件的情况下, 仍然存在无穷多种 T 的分布方式{G}. 这里必然存在一个图 G, 使得在 G 中有最多的点, 它们的横坐标相同. 我们把这些点的集合记为R. 事实上, R 不仅割开了从源点到汇点的所有路径, 而且就是我们要找的答案.
我们得到了结果, 但是这个描述太繁琐了, 虽然在几何上体现的很漂亮, 而且神奇. 那么, 这个神奇的R有没有一个简单的文字描述呢?
考虑同时出现在R中的两个点, 它们可以在同一个 x 坐标上, 意味着它们之间不存在偏序关系. 因此我们找到了 R 的一个简单描述: R是一个含有最多元素的集合, 这些元素在这个拓扑结构中不存在偏序关系.
Answer 2.1
对于任意一个动态规划问题, 其模型都是幂等半环上面的一个拓扑结构. 一个问题有不同的状态压缩方案, 我们把方案的集合记做 {T}, 每一个 T 代表一个状态压缩方案产生的拓扑结构. 我们定义一个函数f, f(T) 是 T 中含有最多元素的集合, 这些元素在这个拓扑结构中不存在偏序关系.
那么, 动态规划问题的空间复杂度, 就是f(T)的最小值.
Kruskal 则作为树形结构存储状态, 最多的时候可能有O(n)个状态. 在最小生成树这个模型里面有一个地方比较巧, 就是这 O(n) 个状态里面的点不会重复, 所以所有状态加起来只需要O(n)的空间. 注意, 这个空间复杂度, 也是在新状态替换掉原来状态达成的. Kruskal 的空间复杂度是 O(n)*s, 其中 O(n)*s = O(n).
再考虑最长公共子序列(LCS). answer 1.1 中我们谈到, 每次只需要求两个子串长度和是 k 的所有状态(步骤 k ). 事实上, 我们在求步骤 k 的时候, 需要用到的当前状态只有第 k-1 步和第 k-2 步, 因此我们只需要同时保存两个连续步骤的所有空间就可以了. LCS 的空间复杂度是O(n).
一个很直观的问题就是, 是不是所有动态规划问题, 都可以在中间过程中把先前状态删掉, 从而省下空间代价呢?
答案是肯定的. 考虑状态空间的拓扑结构, 只要从源点 s 到汇点 t 的任意一条路径上, 仅保留所有状态里面已经遍历的"最后一个"状态, 就可以保证留下剩下的遍历需要所有的空间了. 事实上, "最后一个"是拓扑定义的结果, 假设一个路径上有前 k 个状态被遍历, 后面则没有 (因为遍历的顺序是拓扑顺序, 因此遍历的状态前面不存在未遍历的状态), 我们剩下的遍历只需要最后一个当前已经被遍历的状态.
我们还剩下一个细节没有处理. 注意, 在动态规划问题中, 不仅合并(merge)是由算法架构定义的, 状态的遍历顺序也是. 那么, 我们能否找到一个最"好"的状态遍历顺序, 使得我们从遍历开始到遍历结束所需要的空间代价最低呢? 我们考虑从源点 s 到汇点 t 的任意一条路径上至少需要有一个状态, 这种情况下所有状态所需空间的最小值.
我们尝试用分割的观点来"想象"一下, 一个解的集合是一个什么样的结构. 事实上, 对于任意一个拓扑结构 T 和任意一个给定方向的向量 u , 都可以把它映射到一个二维的图上, 使得所有的状态转移向量(箭头)和 u 的夹角小于90度. 换言之, 任意一个 T 中的向量 v 都满足 u*v > 0. 现在我们需要找到一个最小的状态的集合, 使得它可以割开从源点到汇点的所有路径.
为了直观, 我们把 u 想象成 x 轴, 把二维空间想象成平面直角坐标系. 注意到, 给定任意 T 和 x 轴的方向 , 在满足上述条件的情况下, 仍然存在无穷多种 T 的分布方式{G}. 这里必然存在一个图 G, 使得在 G 中有最多的点, 它们的横坐标相同. 我们把这些点的集合记为R. 事实上, R 不仅割开了从源点到汇点的所有路径, 而且就是我们要找的答案.
我们得到了结果, 但是这个描述太繁琐了, 虽然在几何上体现的很漂亮, 而且神奇. 那么, 这个神奇的R有没有一个简单的文字描述呢?
考虑同时出现在R中的两个点, 它们可以在同一个 x 坐标上, 意味着它们之间不存在偏序关系. 因此我们找到了 R 的一个简单描述: R是一个含有最多元素的集合, 这些元素在这个拓扑结构中不存在偏序关系.
Answer 2.1
对于任意一个动态规划问题, 其模型都是幂等半环上面的一个拓扑结构. 一个问题有不同的状态压缩方案, 我们把方案的集合记做 {T}, 每一个 T 代表一个状态压缩方案产生的拓扑结构. 我们定义一个函数f, f(T) 是 T 中含有最多元素的集合, 这些元素在这个拓扑结构中不存在偏序关系.
那么, 动态规划问题的空间复杂度, 就是f(T)的最小值.
$$ complexity = \underset{T \in \{T\}} {\mathrm{min}} ~f(T) $$
完.
RSS Feed
