动机
矩阵乘法满足结合律,因此相容的矩阵可以用不同的括号化方式相乘,而数学上的乘积不变。然而标量乘法的次数可能相差悬殊。动态规划通过记录每个连续区间的最优代价,避免枚举所有括号化方式。状态必须同时保留两个端点:链中间的一个矩阵可以参与许多维数和代价各不相同的子问题。
本单元的目标函数统计标准三重循环矩阵乘法算法中的标量乘法次数,不统计加法、内存访问、数值舍入误差或经过优化的硬件操作。在这一代价模型下最优的顺序,在实际实现中未必最快。
定义
定义 2.2.1
(矩阵链与区间代价)
设 为矩阵,,其中 的维数为 ,且每个 都是正整数。无论如何括号化,每个连续乘积 的维数都是 。在标准算法中,将 矩阵与 矩阵相乘需要 次标量乘法。
对 ,令 为对 完全括号化的最小代价。单个矩阵无需乘法,故 。对 ,最后一次运算必定在某个 ()之后将区间分开,其两个输入分别是左、右两个连续子链的乘积。
定理
定理 2.2.2
(最优子结构与递推式)
对 ,
为每个区间记录任一取得最小值的分割点,即可重构出一个最优括号化方式。
定理 2.2.3
(动态规划的代价)
按区间长度递增的顺序填表,共计算 个候选分割,使用 次算术运算和 个表项,并得到最优值。为每个区间再存储一个取得最小值的分割点,需要另外 个表项。
证明思路或证明
证明
(最后分割与最优子结构)
固定一个区间和最后一次分割 。由结合律,两个操作数恰为左、右子链的乘积。它们的维数分别为 和 ,因此最后一次乘法的代价如上式所示,与两个子链各自如何括号化无关。若某个声称最优的完全括号化使用了非最优的左子链,则把它换成代价更低的括号化,维数和最后一次乘法的代价都不变,这与最优性矛盾。对右子链的论证相同。
因此,以 为最后分割的每个括号化,其代价至少等于递推式中对应的候选值。反之,为两个严格更短的子链各取最优括号化,再将所得结果相乘,恰好达到该候选值。对所有可能的最后分割取最小值,即证等式成立。该论证对区间长度用归纳法,从单个矩阵开始,是良基的。
重构时,为每个区间保存一个取得最小值的 。递归地重构左、右区间,并在它们的乘积外加上括号。每次递归调用都使区间长度减小,因此必然终止。递推式的证明说明重构所得的代价等于表中的值;若有并列最优,可任意取舍,不同取舍可能得到不同的最优括号化。
证明透视
为什么替换是可行的
子链结果的维数取决于它的端点,而不取决于其内部的括号。因此换成代价更低的括号化,不会改变最后一次乘法的代价。正是这一不变性使最优子结构的论证成立。该假设只用在一处:最后一次乘法的代价 不可取决于两个子链是如何建成的。论证按区间长度归纳而告完结,因为两个子链都严格更短,而单个矩阵是代价为零的基础情形;并列最优并无影响,因为只断言最小值。若合并代价确实取决于内部构造,较便宜的子链便可能被一个较贵、却使最后一步更便宜的子链取代,递推式就不再是等式。
证明
(候选分割与表项的计数)
长度为 的区间有 个可能的分割,这样的区间共有 个。它们对 求和等于 :每个候选唯一对应三个下标 ,等价地,对应从 中选出的三个互不相同的切分位置。表中相关的表项共 个。按长度递增填表,可保证两个子问题在使用前已经算出。若维数以二进制编码,表项可能超出一个机器字;算术运算次数并不自动等于位复杂度上界。
例题详解
例题 2.2.4
(括号化方式的巨大差异)
设三个矩阵的维数依次为 、 和 。先乘前两个再乘第三个,代价为 。先乘后两个,代价为 。两种方式的结果维数都是 ,但前一种顺序所用的标量乘法次数仅为后者的十分之一。
例题 2.2.5
(四个矩阵的表)
取维数 。长度为二的区间代价为 、、。长度为三时,,。最后, 的三个候选值为 、 和 。最优值为 ,对应分割 :。
例题 2.2.6
(并列的情形)
若三个矩阵都是 ,两种括号化的代价均为 。两个最后分割都是最小值点。保存第一个取得最小值的下标,就得到一个正确的答案;算法并不要求列出所有最优解。
常见错误
反例模式
选择当前代价最小的乘积
取维数 。唯一一个代价最小的初始相邻乘积是 ,代价为 。做完这次乘法后,剩余维数为 ;下一步代价最小的乘积需要 ,最后一次乘法需要 ,总计 。反之,先乘 的代价为 ,剩余维数为 。接着乘剩下的前两个矩阵,代价为 ,最后一次乘法的代价为 。总计 。因此,选择当前代价最小的乘积并不总是最优的;递推式考察的是每一种可能的最后分割。
常见错误
(混淆分割处的维数)
对区间 在 之后分割的候选,最后一次乘法的两个操作数维数是 和 ,所以代价是 ,而不是 。对 ,维数为 和 ,唯一的分割是 ,代价为 ;若误用 ,便得到 ,这并非维数相配的乘法。子链乘积的外侧维数由其端点决定。此外,表项是代价,而不是矩阵:要得到矩阵乘积,必须先重构出运算顺序,再实际执行矩阵乘法。
填表时不遗漏依赖关系
先将所有对角线表项初始化为零。然后依次处理长度 。对每个起点下标 ( 从 到 ),令 ,并计算每个分割 。两个子区间的长度都小于 ,所以它们的表项已经可用。令 为最小的候选值,并保存取得该值的一个下标。答案为 。当 时,关于长度的循环不会执行,答案就是已经初始化的零。
同一长度内各表项的计算顺序无关紧要,因为它们只依赖更短的区间。相反,若不检查依赖关系而按行从左到右填表,可能读到尚未算出的表项。依赖图能把这一点看得很清楚:从每个状态向某个候选所需的状态连边。所有这些边都指向更短的区间,所以区间长度就是一个拓扑序。尽管递推式引用的是同一张表,它并不是循环定义。
例题 2.2.7
(由保存的分割点重构)
在四个矩阵的例子中,区间 保存的分割点为 。递归得到区间 和 ;它们都只有一个可能的分割。因此重构输出 。为独立验证,前两次中间乘法的代价为 和 ,结果的维数分别为 和 。最后一次乘法的代价为 ,总和为 ,与表中的值一致。
仅凭代价表,有时也可以通过重新计算各个候选值,找到与所存最小值相符者,从而恢复分割点。保存分割点可以免去这一额外搜索,并使并列情形的处理方式明确。当多个分割下标取得相同代价时,任取其一就足以重构出一个最优解。列出所有最优括号化则是另一个输出问题:即使代价表的大小是二次的,最优括号化的个数也可能非常大。
为什么局部选择并不充分
代价最小的相邻乘法看上去很有吸引力,因为它的代价立即可知。但这次乘积产生了新的维数,会改变后续乘法的代价。在上面的反例中,代价最小的第一步留下了一对较不利的维数。若要用交换论证,就必须证明:把某个全局最优解的第一步换成代价最小的相邻对,绝不会增加此后的总代价。这个明确的反例证明,对这一规则而言,这样的一般性论证不可能存在。
动态规划避免了对第一步的猜测,而是按最后一次乘法对完全括号化方式进行分类。一旦分割确定,两个子乘积的维数就已知,最后一步的代价因而与它们内部的顺序无关。递推式在比较候选值之前,已经计入了两个子问题和最后一次乘法的代价。这正是它的局部比较是安全的、而只比较眼前的乘法代价却不安全的确切原因。
完全括号化乘积的可能数目随 迅速增长,而区间的数目只是二次的。许多候选的完全括号化使用同一个区间,所以制表时直接复用该区间的最优解,而不是重复求解。立方量级的运算次数包含了所有区间的所有分割选择,并不需要枚举所有完全括号化。若使用相同的状态与递推式做记忆化递归,只要每个状态至多计算一次,状态数和分割数的渐近量级相同。
输入与模型的限制
维数必须按原顺序匹配: 的列数必须等于 的行数。否则整个乘积没有定义,此递推式也不能修复这样的输入。
常见错误
(为节省乘法而调换矩阵顺序)
结合律只允许括号移动,不允许调换矩阵。设 为 矩阵、 为 矩阵:乘积 有定义,大小为 ,但 没有定义,因为 有 列而 只有 行。因此按大小为矩阵链排序,会改变问题或使它失去意义;递推式只是为给定的顺序选择括号。
上述计数使用的是 与 矩阵相乘的标准代价 。其他乘法算法,或对加法另行计费的模型,会改变递推式中的局部代价。只有当替换性质仍然成立时,同样的动态规划结构才依然有效:相关的结果大小以及合并子结果的代价,必须取决于状态中所包含的信息。在数值浮点运算中,改变括号还可能改变舍入后的结果,尽管精确的矩阵乘法满足结合律。本笔记优化的是在所声明的标量乘法模型下的精确代数乘积。
立方量级的运算次数上界假设表项上的算术运算代价为单位成本。若输入维数很大,则每个代价是可能远大于任一维数的整数,精确比较与加法的位运算代价便取决于其长度。使用任意精度整数时,递推式仍然正确;机器模型只影响运行时间的核算。每当某个数值参数是以二进制给出、而不是真有那么多个对象的列表时,这一区分都很有用。
理解候选数目
有一种直接的方式可以看出这个二项式系数。用三个切分位置 表示一个候选,这三个位置取自 且满足 。反之,任意三个递增的切分位置恰好确定一个区间和一个合法分割。因此候选数目就是 个位置中三元子集的个数。对 ,得到十个,与逐一统计的长度为二的三个、长度为三的四个、长度为四的三个候选一致。这一计数针对的是比较的候选,而不是实际求矩阵乘积时所用的标量乘法。
概念视角组合
括号化即多边形的三角剖分
当 ,把切分位置 当作凸 边形的顶点。矩阵 对应连接顶点 与 的边,另有一条封闭边连接 与 。 的每个完全括号化,就是这个多边形的一个三角剖分:区间 在 之后的最后分割,是顶点为 的三角形,其代价恰为 ;两个子链则是被边 和 截出的两个子多边形。因此括号化的总代价等于各三角形的 之和,递推式就是最小权三角剖分的标准递推式,而上面数出的 的三元子集,正是所有可能的三角形。
实现取最小值时,由于区间长度大于一,每个区间至少有一个候选。将其最佳值初始化为第一个候选,再与其余候选比较;对角线单独处理。这样可避免把未初始化的表值与真正为零的代价混淆。正的维数保证任何非平凡乘法在此模型中的代价为正,不过一旦给定合法的局部代价,算法的归纳证明并不需要这一正性。
这一证明还说明,同样的一般技术只有在仔细选定状态之后才适用于其他区间问题。若合并两个子解的代价取决于某个会随其内部构造而变化的隐藏性质,那么只存储最小代价,可能丢掉一个较贵、却使后续合并便宜得多的子解。此处不存在这样的隐藏维度: 的每一种括号化都得到相同的矩阵维数。这一事实应当在写出递推式之前就加以确立,而不是当作递推式本身的推论来假定。
总结
每个括号化都有一个最后分割。两个所得的子链可以独立优化,因为它们的结果维数由端点所决定。按区间长度递增计算递推式,只需立方量级的算术运算,而记录下来的分割点可重构出一个最优顺序。
练习
快速检查
(对维数 计算两种括号化的代价,并选出一个最优解。)
分别计算两种括号化的代价。
解答 · 答案
先乘左边的代价为 ;先乘右边的代价为 。先乘左边是最优的。
快速检查
( 是多少?为什么?)
回想递推式对只含一个矩阵的区间怎样规定。
解答 · 答案
它等于零,因为单个矩阵本身就是它自己的乘积,不需要任何标量乘法。
快速检查
(当 时,该表共计算多少个候选分割?)
分别数出每种区间长度的候选数目,再相加。
解答 · 答案
个数为 :长度为二的区间有三个候选,长度为三的有四个,长度为四的有三个。
快速检查
(若每个矩阵都是 ,则 个矩阵的任一完全括号化的代价是多少?)
先数二元矩阵乘法的次数。
解答 · 答案
每个完全括号化恰好使用 次二元矩阵乘法,每次代价为 ,所以总代价为 。