矩阵相乘问题.docx

符号三角形问题问题描述:给定n个矩阵{A1,A2,...,An},其中Ai与Ai+1是可乘的,i=1,2,...,n-1,求矩阵相乘至少需要多少次数乘?输入:A110*100,A2100*5,A35*50三、输出:图一为A1*A2*A3至少需要的次数乘数值算法描述:寻找最优子结构此问题最难的地方在于找到最优子结构。对乘积A1A2...An的任意加括号方法都会将序列在某个地方分成两部分,也就是最后一次乘法计算的地方,我们将这个位置记为k,也就是说首先计算A1...Ak和Ak+1...An,然后再将这两部分的结果相乘。最优子结构如下:假设A1A2...An的一个最优加括号把乘积在Ak和Ak+1间分开,则前缀子链A1...Ak的加括号方式必定为A1...Ak的一个最优加括号,后缀子链同理。一开始并不知道k的确切位置,需要遍历所有位置以保证找到合适的k来分割乘积。算法设计:构造递归解设m[i,j]为矩阵链Ai...Aj的最优解的代价,则构建辅助表,解决重叠子问题从第二步的递归式可以发现解的过程中会有很多重叠子问题,可以用一个nXn维的辅助表m[n][n]s[n][n]分别表示最优乘积代价及其分割位置k。辅助表s[n][n]可以由2种方法构造,一种是自底向上填表构建,该方法要求按照递增的方式逐步填写子问题的解,也就是先计算长度为2的所有矩阵链的解,然后计算长度3的矩阵链,直到长度n;另一种是自顶向下填表的备忘录法,该方法将表的每个元素初始化为某特殊值(本问题中可以将最优乘积代价设置为一极大值),以表示待计算,在递归的过程中逐个填入遇到的子问题的解。程序:#include<iostream>usingnamespacestd;constintN=4;//p为矩阵链,p[0],p[1]代表第一个矩阵的行数和列数,p[1],p[2]代表第二个矩阵的行数和列数......length为p的长度//所以如果有六个矩阵,length=7,m为存储最优结果的二维矩阵,s为存储选择最优结果路线的//二维矩阵voidMatrixChainOrder(int*p,intm[N][N],ints[N][N],intlength){intn=length-1;intl,i,j,k,q=0;//m[i][i]只有一个矩阵,所以相乘次数为0,即m[i][i]=0;for(i=1;i<length;i++){m[i][i]=0;}//l表示矩阵链的长度//l=2时,计算m[i,i+1],i=1,2,...,n-1(长度l=2的链的最小代价)for(l=2;l