首页 > 代码库 > 算法导论------------------动态规划之矩阵链问题
算法导论------------------动态规划之矩阵链问题
【问题描述】
给定有n个连乘矩阵的维数,要求计算其采用最优计算次序时所用的乘法次数,即所要求计算的乘法次数最少。例如,给定三个连乘矩阵{A1,A2,A3}的维数分别是10*100,100*5和5*50,采用(A1A2)A3,乘法次数为10*100*5+10*5*50=7500次,而采用A1(A2A3),乘法次数为100*5*50+10*100*50=75000次乘法,显然,最好的次序是(A1A2)A3,乘法次数为7500次。
设m[i,j]为矩阵链Ai...Aj的最优解的代价,则
┌ 0 如果i = j
m[i,j] =
从第二步的递归式可以发现解的过程中会有很多重叠子问题,可以用一个nXn维的辅助表m[n][n] s[n][n]分别表示最优乘积代价及其分割位置k 。
给定有n个连乘矩阵的维数,要求计算其采用最优计算次序时所用的乘法次数,即所要求计算的乘法次数最少。例如,给定三个连乘矩阵{A1,A2,A3}的维数分别是10*100,100*5和5*50,采用(A1A2)A3,乘法次数为10*100*5+10*5*50=7500次,而采用A1(A2A3),乘法次数为100*5*50+10*100*50=75000次乘法,显然,最好的次序是(A1A2)A3,乘法次数为7500次。
分析:
矩阵链乘法问题描述:给定由n个矩阵构成的序列[A1,A2,...,An],对乘积A1A2...An,找到最小化乘法次数的加括号方法。
1)寻找最优子结构
此问题最难的地方在于找到最优子结构。对乘积A1A2...An的任意加括号方法都会将序列在某个地方分成两部分,也就是最后一次乘法计算的地方,我们将这个位置记为k,也就是说首先计算A1...Ak和Ak+1...An,然后再将这两部分的结果相乘。
最优子结构如下:假设A1A2...An的一个最优加括号把乘积在Ak和Ak+1间分开,则前缀子链A1...Ak的加括号方式必定为A1...Ak的一个最优加括号,后缀子链同理。一开始并不知道k的确切位置,需要遍历所有位置以保证找到合适的k来分割乘积。
2)构造递归解设m[i,j]为矩阵链Ai...Aj的最优解的代价,则
┌ 0 如果i = j
m[i,j] =
└ min(i≤k<j) {m[i,k] + m[k+1,j] + p[i-1] * p[k] *p[j] } 如果i<j
3)构建辅助表,解决重叠子问题从第二步的递归式可以发现解的过程中会有很多重叠子问题,可以用一个nXn维的辅助表m[n][n] s[n][n]分别表示最优乘积代价及其分割位置k 。
辅助表s[n][n]可以由2种方法构造,一种是自底向上填表构建,该方法要求按照递增的方式逐步填写子问题的解,也就是先计算长度为2的所有矩阵链的解,然后计算长度3的矩阵链,直到长度n;另一种是自顶向下填表的备忘录法,该方法将表的每个元素初始化为某特殊值(本问题中可以将最优乘积代价设置为一极大值),以表示待计算,在递归的过程中逐个填入遇到的子问题的解。
这里我使用c++中容器来解决,一般使用的数组下标带来的问题极其容易出差,还是c++比较方便,解决数组必须用常量来表示数组下标。不废话了,思路自己看算法导论树上的讲解,搞清解决问题原理写出代码就轻而易举。
#include<iostream> #include<vector> #include<algorithm> #include<iterator> using namespace std; pair<vector<vector<int>>,vector<vector<int>>> matrix_chain_order(vector<int> p) { int n = p.size(); vector<vector<int>> m(n, vector<int>(n, 0));//vector的vector相当于数组的数组,即二维数组m[][] vector<vector<int>> s(n, vector<int>(n, 0));//同上s[][] for (int len = 2; len < n; len++) { for (int i = 1; i < n - len + 1; ++i) { int j = i + len - 1; m[i][j] = 0x7fffffff; for (int k = i; k <= j-1; ++k) { int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; if (q < m[i][j]) { m[i][j] = q; s[i][j] = k; } } } } return make_pair(m, s); } //打印最优解 void print_Optimal_Parens(vector<vector<int> > s, int i, int j) { if (i == j) cout << "A" << i; else { cout << "("; print_Optimal_Parens(s, i, s[i][j]); print_Optimal_Parens(s, s[i][j] + 1, j); cout << ")"; } } //一般递归方法 int recursive_matrix_chain(vector<int> p, int i, int j) { int n = p.size(); vector<vector<int>> m(n, vector<int>(n, 0)); if (i == j) return 0; m[i][j] = 0x7fffffff; for (int k = i; k < j; k++) { int q = recursive_matrix_chain(p, i, k) + recursive_matrix_chain(p, k + 1, j) + p[i - 1] * p[k] * p[j]; if (q < m[i][j]) m[i][j] = q; } return m[i][j]; } //带备忘的自顶向下的递归方法实现 int look_up_chain(vector<vector<int>> m, vector<int> p, int i, int j) { if (m[i][j] < 0x7fffffff)//如果m[i][j]不是无穷大则说明m[i][j]已经被下一层的LookUpChain计算出来 return m[i][j]; if (i == j) m[i][j] = 0; for (int k = i; k < j; k++) { int q = look_up_chain(m, p, i, k) + look_up_chain(m, p, k + 1, j) + p[i - 1] * p[k] * p[j]; if (q < m[i][j]) m[i][j] = q; } return m[i][j]; } int memoized_matrix_chain(vector<int> p,int s,int e) { int n = p.size(); vector<vector<int>> m(n, vector<int>(n, 0)); for (int i = 1; i < n; i++) { for (int j = i; j < n; ++j) { m[i][j] = 0x7fffffff; } } return look_up_chain(m, p, s, e); } int main() { vector<int> p = { 30, 35, 15, 5, 10, 20, 25 }; vector<vector<int>> m = matrix_chain_order(p).first; vector<vector<int>> s = matrix_chain_order(p).second; cout << "vector m:" << endl; for (size_t i = 0; i < m.size(); i++) { copy(m[i].begin(), m[i].end(), ostream_iterator<int>(cout, " ")); cout << endl; } cout << "vector s:" << endl; for (size_t i = 0; i <s.size(); i++) { copy(s[i].begin(), s[i].end(), ostream_iterator<int>(cout, " ")); cout << endl; } cout << "输出最优解:————>"; print_Optimal_Parens(s, 1, 6); cout << endl; cout << "--------------------------------------------------" << endl;; vector<vector<int>> m1 = matrix_chain_order(p).first; vector<int> p1 = { 30, 35, 15, 5, 10, 20, 25 }; cout << "普通递归方法求解:"; cout << recursive_matrix_chain(p1, 1, 6) << endl; cout << "带备忘的递归方法求解:"; cout << look_up_chain(m1, p1, 1, 6) << endl; }
算法导论------------------动态规划之矩阵链问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。