实验五 动态规划(2)熟悉矩阵连乘的算法，设计一个动态规划算法解决

一、 实验目的及任务

1. 掌握动态规划算法的基本步骤：找出最优解的性质，并刻画其结构特征；递归地定义最优值；以自底向上的方式计算出最优值；根据计算最优值时得到的信息，构造最优解。
2. 熟悉矩阵连乘的算法，设计一个动态规划算法解决。

二、 实验环境

c++

三、实验内容

给定n个矩阵<A1,A2,…,An>，其中Ai与Ai+1是可乘的，i=1，2…，n。 矩阵 Ai 的维度为 P i-1´ Pi，如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

设计一个动态规划算法确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

随机产生10以上的字符，放入输入文件input.txt，如：P={30，35，15，5，10，20，25}

四、算法描述

伪代码：

 

 

五、算法的执行

由于矩阵乘法要求两个相乘矩阵的维度满足：第一个矩阵的列数要与第二个矩阵的行数相同。所以我们只要用N+1个数字就能表示所有矩阵的维度了，这里我们用 d 来表示这 N+1个数字， 其中di和 di+1分别表示第 i 个矩阵的行数和列数。

六、算法时间复杂度分析

利用动态规划的思想解决矩阵序列连乘问题的算法本身的时间复杂度跟BB 矩阵的计算有关，BB 矩阵需要计算其整个上三角部分，我们逐步推导：

 

第 11 列: 计算B(0,1)B(0,1): 需要 1−0=11−0=1 次计算。

 

第 22 列: 计算B(1,2)B(1,2): 需要 2−1=12−1=1 次计算。

第 22 列: 计算B(0,2)B(0,2): 需要 2−0=22−0=2 次计算。

 

第 33 列: 计算B(2,3)B(2,3): 需要 3−2=13−2=1 次计算。

第 33 列: 计算B(1,3)B(1,3): 需要 3−1=23−1=2 次计算。

第 33 列: 计算B(0,3)B(0,3): 需要 3−0=33−0=3 次计算。

⋮⋮

第 N−1N−1 列: 计算B(N−2,N−1)B(N−2,N−1): 需要 (N−1)−(N−2)=1(N−1)−(N−2)=1 次计算。

第 N−1N−1 列: 计算B(N−3,N−1)B(N−3,N−1): 需要 (N−1)−(N−3)=2(N−1)−(N−3)=2 次计算。

第 N−1N−1 列: 计算B(N−4,N−1)B(N−4,N−1): 需要 (N−1)−(N−4)=3(N−1)−(N−4)=3 次计算。

⋮⋮

第 N−1N−1 列: 计算B(0,N−1)B(0,N−1): 需要 (N−1)−(0)=N−1(N−1)−(0)=N−1 次计算。

所以计算时间复杂度为：

 

虽然算法时间复杂度为O(N3)， 我们只需要存储一个矩阵就可以了，所以空间复杂度是 O(N2)

八、结果分析

源代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<time.h>
#include<stdlib.h>
#include<fstream>
#include<string.h>

using namespace std;
const int MAX = 100;
const int n=10;
int p[MAX+1],m[MAX][MAX],s[MAX][MAX];
int a[n];
void creatInput(){
	srand(time(NULL));
	FILE *p;
	p = fopen("input.txt", "w");
	if (!p){
		cout << "文件打开异常！" << endl;
		return ;
	}
	for (int i = 0; i <= n;++i){
		fprintf(p, "%d\n", rand()%30);
	}
	fclose(p);


}

void readInput(){
	int dl = 0;
	ifstream file("input.txt");
	while(!file.eof()){
		file>>a[dl];
		++dl;
	}
    file.close();

}


void matrixChain()
{
    for(int i=1; i<=n; i++)
        m[i][i]=0;
    for(int r=2; r<=n; r++)
    {
        for(int i=1; i<=n-r+1; i++) 
        {
            int j=i+r-1;
            m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
            s[i][j]=i;
            for(int 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])
                {
                    s[i][j]=k;
                    m[i][j]=t;
                }
            }
        }
    }
}
void traceback(int i,int j)
{
    if(i==j)
        return;
    traceback(i,s[i][j]);
    traceback(s[i][j]+1,j);
    cout<<"Multiply A"<<i<<","<<s[i][j]<<"and A"<<s[i][j]+1<<","<<j<<endl;
}
int main()
{
	creatInput();
	readInput();
	for(int i = 0;i <= n;++i){
		p[i] = a[i];
	}
	for(int j : a)
		cout<<j<<" ";
	cout<<endl;
    matrixChain();
    traceback(1,n);
    cout<<m[1][n]<<endl;
    return 0;
}