矩阵连乘问题
-
分析与动态方程:
分析如下：
????????要计算n个矩阵，A1，A2，…，An，可利用动态规划进行解决。
????????设m[1][n]为A1，A2，…，An连乘的计算量；
????????此问题符合最优子结构问题，即：当[A1，A2，…，An]构成最优的解，连乘次数最少，即m[1][n]最小，则其子问题[A1，A2，…，Ak]与[Ak+1，A2，…，An]（k为常数，1<=k<n,）均为最优解。
????????即m[1][n]=m[1][k]+m[k+1][n]+ P(1_) P(k)P(n)；最小时m[1][k]最小，m[k+1][n]最小；
k表示在第k个元素后面断开,、
P(i)表示第i个元素的列数；P(i_)表示第i个元素的行数
所以有：
P(1_ )表示第1个元素的行数
P(k)表示第k个元素的列数
P(n)表示第n个元素的列数
证明如下：
?反证法：若[A1，A2，…，Ak]不是最优解，则可以找到另外的次序m_[1][k]，使其乘法计算量少于[A1，A2，…，Ak]的乘法计算量m[1][k]
????????则有m_[1][n] < m[1][n];
????????所以m[1][n]不是最小值
这与m[1][n]为最小值，[A1，A2，…，An]构成最优的解矛盾，故此不成立，原结论成立。
????????2. 求解动态规划方程：
当只有一个矩阵时，连乘次数m[1][1]=0;
m[1][2] =? m[1][1]+m[2][2]+?P(1,k)?P(k)P(k+1,n)
?????? ?=? 0+0+?P(1,k)?P(k)P(k+1,n)
?????? ?=? P(1,k)?P(k)P(k+1,n)
m[1][n]= m[1][n]=m[1][k]+m[k+1][n]+?P(1_)?P(k)P(n)；
动态规划方程为：
程序截图为：
????????3. 源代码及注释：
#include<iostream>
#include<vector>
#include<string>
using namespace std;
void MatrixChain(vector<int> &p, int n, vector<vector<int>> &m, vector<vector<int>> &s) {
for (int i = 0; i < n; i++) //规模为1时，i=j,计算量m[i][j]=m[i][i]=0;
m[i][i] = 0;
for (int r = 2; r <= n; r++) //规模为r时，i<j,计算量m[i][j]=min(m[i][k] + m[k][j] + p[i - 1] * p[k] * p[j])
{
for (int i = 0; i < n + 1 - r; i++) //规模为r，开始元素为i,末尾元素j=i+r-1,末尾元素j<=n,等价于i<=n+1-r ,而i是从0开始，后面不加等号
{
int j = i + r -1;
//p数组为连乘矩阵数组，i从0开始，第i+1个元素，其行数为p[i],列数为p[i+1]
//从第一个位置断开的m[i][j]
m[i][j] = m[i][i] + m[i+1][j] + p[i] * p[i+1] * p[j+1];
s[i][j] = i;
/*cout << m[i][j];*/
//从第k个位置断开的m[i][j]
for (int k = 1+i; k < j; k++)
{
//用t表示不同断开位置的连乘次数，t最小时候，对应为当前m[i][j]
int t = m[i][k] + m[k+1][j] + p[i] * p[k+1] * p[j+1];
if (t < m[i][j])
{
m[i][j] = t;
s[i][j] = k; //用s记录断开位置
}
}
}
}
}
void Traceback(int i, int j, vector<vector<int>>& s,string &order)
{
if (i == j) //回归条件
{
order.append("A");
order.append(to_string(i));
}
else //按照最佳断点一分为二，接着继续递归
{
order.append("(");
Traceback(i, s[i][j], s,order);
Traceback(s[i][j] + 1, j, s,order);
order.append(")");
}
}
void creative_matrix() {
int n;
string order; //构造连乘矩阵的输出形式
string out("\n"); //构造最后输出
for (int i = 1; cin >> n;i++) //当输入ctrl+z时，结束输入
{
order = ""; //初始化空串
vector<int>p(n + 1);
vector<vector<int>>m(n);
vector<vector<int>>s(n);
for (int i = 0; i < n; i++) //构造准备数组
{
cin >> p[i];
m[i].resize(n);
s[i].resize(n);
}
cin >> p[n];
MatrixChain(p, n, m, s); //递归求解
Traceback(0, n - 1, s, order); //递归求解
order.erase(order.begin()); //去头括号
order.erase(order.end() - 1); //去尾括号
out += "Case" + to_string(i) + '\n'
+ to_string(m[0][n - 1]) + " " + order + '\n'; //字符串拼接
}
cout << out;
}
int main() {
cout << "请输入数据，按ctrl+z结束输入:" << endl;
creative_matrix();
return 0;
}?
?
?
?
?