动态规划矩阵连乘求最优值和最优解

• 问题描述

矩阵相乘最重要的方法是一般矩阵乘积。它只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义。给定n个矩阵：A1,A2,...,An，其中Ai与Ai+1是可乘的，i=1，2...，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。比如A1（10*100），A2（100*5）,A3（5*50）三个矩阵，相乘次序分别为（（A1*A2）A3）和（A1（A2*A3））时，矩阵相乘的次数分别为7500（10*100*5+10*5*50）和75000(100*5*50+100*50*10)，所以我们需要找到相乘次数最少的矩阵相乘次数（最优值）和矩阵相乘次序（最优解）。

• 基本思路

递归公式

m[i][j]=m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]

这里的i是第一个相乘矩阵的序列数，j是最后一个所乘的矩阵序列数，其中k是最后一次相乘时序列数i到j中间的任意一个断点数。

m[i][j]存放的是从第i个矩阵到第j个矩阵的矩阵连乘的计算次数

实例：

例:现在有六个矩阵相乘，分别是A1、A2、A3、A4、A5、A6，矩阵的行数和列数分别是A1(30,35)、A2（35，15）、A3（15,5）、A4(5,10)、A5(10,20)、A6(20,25),则六个矩阵相乘经过计算解得最优值为：15125，且最优解为：（A1*（A2*A3））*（（A4*A5）*A6）

笔算过程如下：

过程是分层运算的，只有1个矩阵时、有2个矩阵时、有三个矩阵时、、、

 全部代码如下：

#include<iostream>
using namespace std;

int p[100];
int m[100][100], s[100][100];
int n;
//寻找最优值和断点位置
void matrixchain()
{
    int i, r, j, k;

    //初始化数组
    for (i = 0; i < 100; i++)
    {
        for (j = 0; j < 100; j++)
        {
            m[i][j] = 0;
            s[i][j] = 0;
        }

    }

    for (r = 2; r <= n; r++)//矩阵连乘的规模为r,此时计算的矩阵连乘的个数是r个且是顺序连续并所有的。从2开始，因为只有一个矩阵相乘的次数为0。
    {
        for (i = 1; i <= n - r + 1; i++)//第一个矩阵的下标范围
        {
            j = i + r - 1;//最后一个矩阵的下标范围
            m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];//因为m[i][i]为0，先对m[i][j]赋一个在该位置（第一个断点位置）相连乘的值
            s[i][j] = i;//s[][]存储各子问题的决策点，前面m里面存的是在第一个断点位置的值，所以这里存1
            for (k = i + 1; k < j; k++)//寻找在最优位置断点的最优值
            {
                int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (t < m[i][j])
                {
                    m[i][j] = t;//将最优值赋给m
                    s[i][j] = k;//记录断点位置
                }
            }
        }
    }
}
//寻找最优解
void print(int i, int j)
{
    if (i == j)
    {
        cout << "A[" << i << "]";
        return;
    }

    cout << "(";
    print(i, s[i][j]);
    cout << "*";
    print(s[i][j] + 1, j);
    cout << ")";
}

int main()
{
    cout << "请输入矩阵的个数n : " << endl;
    cin >> n;
    int i, j;
    cout << "请依次输入每个矩阵的行数和最后一个矩阵的列数：" << endl;
    for (i = 0; i <= n; i++)
        cin >> p[i];//将第一个矩阵的列和第二个矩阵的行的下标置为相同的了
    matrixchain();
    cout << "最优值为：" << m[1][n] << endl;
    cout << "最优解计算方法为：";
    print(1, n);
    cout << endl;
    return 0;
}

结果如图：