连续执行多个矩阵变换时,保持矩阵先后顺序不变,改变括号结合位置就可能大幅改变计算量。中间矩阵的行列规模不同,因此不能只数共有多少个矩阵。
规则与边界
给定一串兼容矩阵维度,p乘q矩阵与q乘r矩阵相乘需要pqr次标量乘法。对每个连续子链枚举最后一次分割位置,把左右子链最少成本加上合并成本,选择总数最小的括号结构。相同成本取分割位置较小者。
本例记录
六个矩阵编号零至五,维度依次为[[18, 22], [22, 19], [19, 24], [24, 8], [8, 2], [2, 13]]。
子链起点 | 终点 | 最少乘法数 | 最后分割位置 | 括号式 0 | 0 | 0 | None | A0 1 | 1 | 0 | None | A1 2 | 2 | 0 | None | A2 3 | 3 | 0 | None | A3 4 | 4 | 0 | None | A4 5 | 5 | 0 | None | A5 0 | 1 | 7524 | 0 | (A0×A1) 1 | 2 | 10032 | 1 | (A1×A2) 2 | 3 | 3648 | 2 | (A2×A3) 3 | 4 | 384 | 3 | (A3×A4) 4 | 5 | 208 | 4 | (A4×A5) 0 | 2 | 15732 | 1 | ((A0×A1)×A2) 1 | 3 | 6992 | 1 | (A1×(A2×A3)) 2 | 4 | 1296 | 2 | (A2×(A3×A4)) 3 | 5 | 1008 | 4 | ((A3×A4)×A5) 0 | 3 | 10160 | 0 | (A0×(A1×(A2×A3))) 1 | 4 | 2132 | 1 | (A1×(A2×(A3×A4))) 2 | 5 | 1790 | 4 | ((A2×(A3×A4))×A5) 0 | 4 | 2924 | 0 | (A0×(A1×(A2×(A3×A4)))) 1 | 5 | 2704 | 4 | ((A1×(A2×(A3×A4)))×A5) 0 | 5 | 3392 | 4 | ((A0×(A1×(A2×(A3×A4))))×A5)
表中编号只标记本例对象,不表示排名或另一组数据中的身份。先确认输入单位与边界约定,再逐步核对中间值。零、空结果和不存在是不同状态,不能因为显示相近就互相替代;分数用精确形式保留,便于重新演算。
复核方法
结果必须保留原来的矩阵排列,只允许改变括号,不能把矩阵交换顺序。每次合并的内部维度应相等,最终维度由第一个矩阵的行数和最后一个矩阵的列数决定。
从最短的两矩阵子链开始填表,再逐渐扩大范围。可以穷举较短链的全部括号验证动态规划答案。若所有变换都是相同的固定小矩阵,计算量差异可能不明显,但当包含长宽差异很大的矩阵时,结合顺序就值得明确检查。
能说明什么
这里计算普通稠密矩阵乘法的标量乘法次数,没有把缓存、并行、稀疏结构或临时内存成本计入。精确算术下结合律成立,浮点实现换括号后可能有舍入差异,因此少乘法不代表所有实际效果都完全相同。
这份记录用于理解明确规则下的游戏机制。改变输入后,结果也应随之重新计算;若操作规则不同,应先把新规则写清再比较。可以从一两个步骤手算开始,找出第一处差异,而不是只对照最后一个数值。全部中间记录都属于当前案例,不能直接当成其他场景的固定答案。
