第4-6课：矩阵链乘问题
source link: https://blog.csdn.net/orbit/article/details/108729356
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
第4-6课：矩阵链乘问题
这一课介绍的矩阵链乘问题，是区间类型动态规划的典型例子，区间类型的动态规划是在线性动态规划基础上的扩展。我的理解是，这个扩展就是将固定的线性问题变成一个变长的线性问题，也就是说，所谓的区间动态规划，就是在一个可选择的线性区间中寻找某种最优的结果，而线性区间长度本身也是可变化的，最优结果的组合也是可变化的，需要在两重变化中寻找最优解。除了矩阵链乘问题，此类问题的典型例子还有石子合并问题、能量项链问题、最优排序二叉树问题等。除此之外，前几年非常火的多边形三角剖分问题，也被归纳为区间动态规划类型的题目。
《算法导论》一书在介绍动态规划问题时，举了一个矩阵链乘（Matrix-chain Multiplication）的例子。我知道很多读者害怕公式，看见《矩阵论》就头疼，但是不要怕，这个题目只涉及了一个简单的概念，就是矩阵的相容性（Compatible）。矩阵 A 和 B 能够相乘，前提是矩阵 A 和矩阵 B 必须相容，所谓的相容，就是矩阵 A 的列数等于矩阵 B 的行数。假设矩阵 A 是 $p\times q$ 的矩阵，矩阵 B 是 $q\times r$ 的矩阵，则矩阵 A 和矩阵 B 的乘积是一个 $p \times r$ 的矩阵。计算这个乘积需要 $p\times q\times r$ 次标量乘法计算和若干次加法，其计算量的主要代价就是这 $p\times q\times r$ 次乘法计算。
对于一组满足相容性条件（顺序）排列的矩阵做链乘，无论选择中间哪两个矩阵先计算，其结果都能与剩下的矩阵继续保持相容性条件，这是一个很重要的前提，因为调整矩阵的位置会破坏相容性。但是，在矩阵
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK