基于四边形不等式的矩阵连乘优化算法

本文以四边形不等式优化矩阵连乘为例,阐述了如何利用四边形不等式,减少动态规划过程中的状态转移数,从而整体上降低算法的时间复杂度,使其更能够适应大规模计算。本文使用的优化方法具有通用性,对于状态转移方程与矩阵连乘问题相似且满足四边形不等式的动态规划问题,都可以采用与本文相同的优化方法。