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