这是算法导论动态规划中的一个问题问题简述如下: 我们在求解矩阵相乘时通常会有一个最优括号方案来对矩阵进行顺序相乘, 这样会减少大量的计算时间
我们知道矩阵 A*B 相乘, 只能是当矩阵 A 的列数等于矩阵 B 的行数时才能进行相乘, 且假设 A.B = C,A 为 p×q 规模的矩阵, B 为 q×r 的矩阵, 则乘积 C 的规模为 p×r 的矩阵计算 A.B 所需的时间由乘法次数决定, 即 pqr
例如: 有三个矩阵的规模分别为: A = 10×100,B = 100×5,C = 5×50 如果按顺序 (AB)C 计算, 则需要 10×100×5 + 10×5×50 = 7500 次乘法, 如果按顺序 A(BC) 计算, 则需要 100×5×50 + 10×100×50 = 75000 次乘法... 所以, 按第一种顺序计算矩阵链乘积要比第二种快非常多
矩阵链乘法问题可描述如下: 给定 n 个矩阵的链 < A1,A2,...,An>, 矩阵 Ai 的规模为 pi - 1×pi(1 i n), 求完全括号化方案, 使得计算乘积 A1A2...An 所需标量乘法次数最少
分析问题描述可知道, 我们假设在矩阵链乘中找到一个合适的切割点进行括号化, 可得到问题的最优括号方案, 然后对切割点的两边的子问题用相同的方法独立求解, 不断进行下去, 则最终将得到原问题的最优解这就是该问题的最优子结构
构造递归公式: 令 m[i][j] 表示计算矩阵 Ai...j 所需标量乘法次数的最小值, 那么, 原问题的最优解 计算 Ai...n 所需的最低代价就是 m[1][n]
对于 i = j 时, 矩阵链只包含唯一的矩阵 Ai...i = Ai , 不需要做任何标量乘法运算若 i < j, 利用最优子结构来计算 m[i][j]如前面假设 Ai,Ai + 1,...,Aj 的最优括号化方案的分割点在矩阵的 Ak 和 Ak + 1 之间, 其中 i k < j 那么, m[i][j]就等于计算 Ai...k 和 Ak + 1...j 的代价加上两者相乘的代价的最小值由于矩阵 Ai 的大小为 pi×pi + 1, 易知 Ak + 1...j 相乘的代价为 pi.pk + 1.pj + 1 次标量乘法运算因此, 得到:
m[i][j] = m[i][k] + m[k + 1][j] + p[i].p[k + 1].p[j + 1]
由于 k 值取法只有 j - i 种可能的取值, 即 k = i, i + 1, ..., j 检查所有可能的情况, 找到最优, 因此递归公式变为:
- ( 0, i = j;
- m[i][j] = {
- ( min(m[i][k] + m[k + 1][j] + p[i].p[k + 1].p[j + 1]), i < j.
O(n^3)迭代解法:
- #include <iostream>
- #include <vector>
- class Solution {
- public:
- std::vector<std::vector<int> > MatrixChainOrder(std::vector<int>& p)
- {
- const int n = p.size() - 1;
- std::vector<std::vector<int> > m(n, std::vector<int> (n));
- for(int i = 0; i < n; i++)
- {
- m[i][i] = 0;
- }
- for(int l = 1; l < n; l++)
- {
- for(int i = 0; i < n - l; i++)
- {
- int j = i + l;
- m[i][j] = INT_MAX - 1;
- for(int k = i; k < j; k++)
- {
- int q = m[i][k] + m[k + 1][j] + p[i]*p[k + 1]*p[j + 1];
- if(q < m[i][j])
- {
- m[i][j] = q;
- }
- }
- }
- }
- return m;
- }
- };
- int main()
- {
- std::vector<int> p{30, 35, 15, 5, 10, 20, 25};
- Solution solve;
- std::vector<std::vector<int> > res = solve.MatrixChainOrder(p);
- for(int i = res.size() - 1; i >= 0; i--)
- {
- for(int j = 0; j <= i; j++)
- std::cout << res[j][i] << ;
- std::cout << std::endl;
- }
- return 0;
- }
递归版感觉有点问题... 所以再研究一段时间
来源: http://www.bubuko.com/infodetail-2499521.html