分治法解决合并排序问题及动态规划解决矩阵连乘和最长公共子序列问题及贪心法
解决哈夫曼编码问题
一、课程设计目的
本次课程设计可以说是我们学完《计算机算法设计与分析》这门课程后的一次综合性训练。
本课程设计的训练的目的是：
1、巩固和掌握计算机算法设计和分析课程的基础知识。
2、培养使用计算机基本算法解决实际问题的能力。
3、提升使用程序设计语言对算法程序的开发、调试和测试能力。
4、对一定的实际问题，能够设计求解算法并分析算法的效率。
5、提高综合运用算法、程序设计语言等能力。
6、掌握文档的书写能力。
二、课程设计内容
1、分治法
（1）合并排序
2、动态规划
（1）矩阵连乘
（2）最长公共子序列
3、贪心法
（1）哈夫曼编码
三、概要设计
1、分治法
基本思想:
将规模为n的问题分解为k个规模较小的子问题，使这些子问题相互独立可分别求解，再将k个子问题的解合并成原问题的解。如子问题的规模仍很大，则反复分解直到问题小到可直接求解为止。在分治法中,子问题的解法通常与原问题相同。
（1）合并排序
[问题描述]
将n个元素排成非递减顺序。
[算法思路]
若n为1，算法终止；否则，将n个待排元素分割成k(k=2)个大致相等子集合A, B, 对每一个子集合分别递归排序,再将排好序的子集归并为一个集合。
2、动态规划
基本思想：
将问题的求解过程化为多步选择，在每一步选择上，列出各种可能的结果(各子问题的可行解)，舍去那些肯定不能成为最优解的局部解。最后一步得到的解必是最优解。求解过程多为自底向上,求解过程产生多个选择序列, 下一步的选择依赖上一步的结果，总能得到最优解。
（1）矩阵连乘
[问题描述]
给定n个矩阵{A1，…，An}，其中Ai与A(i-1)是可相乘的。确定一个计算次序，使计算矩阵连乘积A1…An所需计算量最少。例如，三个矩阵连乘，两种计算顺序(A*B)*C，A*(B*C)。设A为100*1的矩阵，B为1*100的矩阵，C为100*1的矩阵, 则D=A*B为100*100的矩阵, 需乘法次数为10000, D与C相乘，所需乘法次数为1000000, 计算(A*B)*C的总时间长度为1010000。E=B*C需乘法次数为10000, B*C为1*1的矩阵，E与A相乘，所需乘法数为100，计算A*(B*C)的时间长度只有10100。计算(A*B)*C时，还需10000个单元来存储A*B，而A*(B*C)计算过程中,只需用1个单元来存储B*C。
[算法思路]
将步骤化为多步,自底向上,先求出矩阵链长为1的最优计算次序，链长为2的最优次序，…
[最优解结构]
设A[1:n]= A1…An ，最优计算次序在Ak 和A(k+1)间断开，则总计算量=A[1:k]的计算量+A[k+1:n]的计算量+A[1:k]*A[k+1:n]则矩阵子链A[1:k]和A[k+1:n]的计算次序也必最优。
[递推关系]
设计算A[i:j]=Ai …Aj 所需最少次数乘法为m[i][j]，Ai 的维数设为matrix[i].row*matrix[i].col 。
???
?
?<=??+++=<≤j i j i j i m j
k i }col matrix[j].col matrix[k].row matrix[i].1][j]m[k m[i][k]{min 0]][[
[构造最优解]
记m[i][j]的断开位置k 为s[i][j],在计算出m[i][j]后,可由s[i][j]递归构造相应的最优解。 （2）最长公共子序列 [问题描述]
字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列x=“x0，x1，…，x(m-1)”，序列y=“y0，y1，…，y(k-1)”是x 的子序列，存在x 的一个严格递增下标序列
[算法思路]
引进一个二维数组c[][]，用c[i][j]记录x[i]与y[j]的LCS 的长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。由自底向上进行递推计算，那么在计算c[i,j]之前 c[i-1][j-1]，c[i-1][j]与c[i][j-1]均已计算出来。此时我们根据x[i]=y[j]还是x[i]!=y[j]，就可以计算出c[i][j]。
问题的递归式写成：
j i j i y
x y x j and and or j i j i i if if if j i c j i c j i c j i c ≠==>>=??
?
??
--+--=00,0,0]),1[],1,[max(1]1,1[0],[
3、贪心法 基本思想:
将问题的求解过程看作一系列选择，每次选择都是当前状态下的局部最优解。每作一次选择后，所求问题会简化为一个规模更小的子问题。从而通过每一步的最优解逐步达到整体最优解。
（1）哈夫曼编码
[问题描述]
通讯过程中需将传输的信息转换为二进制码。由于英文字母使用频率不同，若频率高的字母对应短的编码，频率低的字母对应长的编码，传输的数据总量就会降低。要求找到一个编码方案，使传输的数据量最少。哈夫曼编码就是一种最佳编码方案。
[算法思路]
1)以n个字母为结点构成n棵仅含一个点的二叉树集合，字母的频率即为结点的权。
2)每次从二叉树集合中找出两个权最小者合并为一棵二叉树：增加一个根结点将这两棵树作为左右子树。新树的权为两棵子树的权之和。
3) 反复进行步骤2)直到只剩一棵树为止。
四、详细设计与实现
1、合并排序
例：
序列分解过程：{8 4 7 3 6 5 2}
{8 4 7 3} {6 5 2}
{8 4} {7 3} {6 5} {2}
初始序列a a[0] a[1] a[2] a[3] a[4] a[5] a[6]
{8} {4} {7} {3} {6} {5} {2}
排序后归并到b {4 8} {7 3} {6 5} {2}
复制到a {4 8} {7 3} {6 5} {2}
排序后归并到b {3 4 7 8} {2 5 6}
复制到a {3 4 7 8} {2 5 6}
排序后归并到b {2 3 4 5 6 7 8}
复制到a {2 3 4 5 6 7 8}
最终结果为：{2 3 4 5 6 7 8}
C++实现代码为：
#include
using namespace std;
void Merge(int a[],int b[],int l,int m,int r)
{//合并a[l:m]和b[m+1:r]存入到b[l:r]中
int i=l,j=m+1,k=l;
while ((i<=m)&&(j<=r))
if (a[i]<=a[j])b[k++]=a[i++];
else b[k++]=a[j++];
if (i>m)
for(int q=j;q<=r;q++)
b[k++]=a[q];
else
for(int q=i;q<=m;q++)
b[k++]=a[q];
}
void Copy(int a[],int b[],int s,int n)
{
for(int i=s;i<=n;i++)
a[i]=b[i];
}
void MergeSort(int a[],int left,int right)
{
int i;
if(left { i=(left+right)/2;//取中点 int b[100]; MergeSort(a,left,i);//递归调用分别对两个字问题排序 MergeSort(a,i+1,right); Merge(a,b,left,i,right);//合并到数组b Copy(a,b,left,right);//复制回数组a } } int main() { int a[100]; int n,i; cout<<"输入元素个数n:"; cin>>n; cout<<"输入一维数组a["< for( i=0;i cin>>a[i]; MergeSort(a,0,n-1); cout<<"输出排序为:"; for ( i=0;i cout< cout< return 0; } 运行截图： 2、矩阵连乘 例： A1 A2 A3 A4 A5 A6 30*35 35*15 15*5 5*10 10*20 20*25 结果为：((A1(A2A3))((A4A5)A6)) C++实现代码： #include #define MAX 100 using namespace std; struct Matrix //矩阵 { int row; //矩阵行数 int col; //矩阵列数 }; //矩阵 Matrix matrix[MAX]; //m[i][j]存储Ai到Aj的最小乘法次数 int m[MAX][MAX]; //s[i][j]存储Ai到Aj之间加括号的位置 int s[MAX][MAX]; //矩阵个数 int n; void MaxtrixChain(Matrix matrix[MAX],int n,int m[MAX][MAX],int s[MAX][MAX]) {//计算m[][]和s[][] 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]+matrix[i].row*matrix[i].col*matrix[j].col; s[i][j]=i; for(int k=i+1;k { int t=m[i][k]+m[k+1][j]+matrix[i].row*matrix[k].col*matrix[j].col; if(t { m[i][j]=t; s[i][j]=k; } } } } void matrixMultiply(Matrix matrix[MAX],int n) { bool flag=false;//标识矩阵的阶数是否要重新输入 int i; cout<<"请输入每个矩阵行数与列数:"< for(i=1;i<=n;i++) { cout<<"A"< cin>>matrix[i].row; cout<<"A"< cin>>matrix[i].col; } //检查Ai的列数是否等于Ai+1的行数 for(i=1;i { if(matrix[i].col!=matrix[i+1].row) { cout<<"输入的矩阵不可乘，请重新输入!"< flag=true; break; } } if(flag) { matrixMultiply(matrix,n); } } //打印加括号后的 void traceback(int i,int j) { if(i==j) { cout<<"A"< } else { cout<<"("; traceback(i,s[i][j]); traceback(s[i][j]+1,j); cout<<")"; } } void main() { //变量m,s初始化 memset(m,0,sizeof(m)); memset(s,0,sizeof(s)); cout<<"请输入矩阵的个数:"< cin>>n; matrixMultiply(matrix,n); MaxtrixChain(matrix,n,m,s); cout<<"加括号之后:"< traceback(1,n); cout< } 运行截图： 3、最长公共子序列 例： x="cbwdabh" y="sdabwyz" c[i][j]：b[i][j]： 最终结果为：dab C++实现代码： #include using namespace std; #define MAX 100 void LCSLength(char *x,char *y,int m,int n,int c[MAX][MAX],int b[MAX][MAX]) {//用b[][]对c[][]中的元素分成三类 int i, j; for(i=0;i<=m;i++) c[i][0]=0; for(j=1;j<=n;j++) c[0][j]=0; for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { if(x[i-1]==y[j-1])//第一类c[][]中的元素 { c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1])//第二类c[][]中元素 { c[i][j]=c[i-1][j]; b[i][j]=2; } else//第三类c[][]中元素 { c[i][j]=c[i][j-1]; b[i][j]=3; } } } } void LCS(int b[MAX][MAX],char *x,int i,int j) { if(i==0||j==0) return; if(b[i][j]==1)//输出第一类元素对应的x[] { LCS(b,x,i-1,j-1); cout< } else if(b[i][j]==2)//输出第二类元素对应的x[] LCS(b,x,i-1,j); else//输出第三类元素对应的x[] LCS(b,x,i,j-1); } void main() { char x[MAX]; char y[MAX] ; cout<<"输入字符串x:"< cin>>x; cout<<"输入字符串y:"< int b[MAX][MAX]; int c[MAX][MAX]; int m,n; m=strlen(x); n=strlen(y); LCSLength(x,y,m,n,c,b); cout<<"最长公共子序列为:"< LCS(b,x,m,n); cout< 运行截图： 4、Hufman 编码 例： a b c d e f 频率：45 13 12 16 9 5 哈夫曼树为： 结果为：a:0 b:101 16 9 5 14 12 13 45 55 25 30 100 1 0 0 1 1 1 1 a c b f e d c:100 d:111 e:1101 f:1100 C++实现代码： #include #include #define MAX 32767; using namespace std; typedef struct//定义哈夫曼结点结构体 { int weight;//权值 int flag;//标识是否有父母结点 int parent;//父母结点 int lchild; //左孩子结点 int rchild;//右孩子结点 }hnodetype; typedef struct //定义哈夫曼编码结构体 { int bit[10];//定义编码数组 int start; char leaf; }hcodetype; void huffman(char cha[],int m[],int n) { int i,j,m1,m2,x1,x2,c,p; hnodetype *huffnode=new hnodetype[2*n-1];//动态分配结构体空间hcodetype *huffcode=new hcodetype[n],cd;//定义 for(i=0;i<2*n-1;i++) //对哈夫曼结点结构体初始化 { huffnode[i].weight=0; huffnode[i].parent=0; huffnode[i].flag=0; huffnode[i].lchild=-1; huffnode[i].rchild=-1; } for(i=0;i { huffnode[i].weight=m[i];//给哈夫曼结点赋权值 huffcode[i].leaf=cha[i];//给哈夫曼编码叶子赋字符} for(i=0;i { m1=m2=MAX; x1=x2=0; for(j=0;j { if (huffnode[j].weight<=m1&&huffnode[j].flag==0) { m2=m1; x2=x1; m1=huffnode[j].weight; x1=j; } else if(huffnode[j].weight<=m2&&huffnode[j].flag==0) { m2=huffnode[j].weight; x2=j; } } huffnode[x1].parent=n+i; huffnode[x2].parent=n+i; huffnode[x1].flag=1; huffnode[x2].flag=1; huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight; huffnode[n+i].lchild=x1; huffnode[n+i].rchild=x2; } for(i=0;i { cd.start=n-1; c=i; p=huffnode[c].parent; while(p!=0)//构建哈夫曼编码权值 { if(huffnode[p].lchild==c) cd.bit[cd.start]=0; else cd.bit[cd.start]=1; cd.start--; c=p; p=huffnode[c].parent; } cout< for(j=cd.start+1;j { huffcode[i].bit[j]=cd.bit[j]; cout< } cout< huffcode[i].start=cd.start; } delete[] huffcode;//释放空间 delete[] huffnode;//释放空间 } void main() { int i=0,n,m[100],k; char cha[100]; cout<<"输入的总字符n:"; cin>>n; k=n; for(i=0;i { cout<<"第"< cin>>cha[i]; cout<<"字符"< cin>>m[i]; } cout<<"每个字符的哈夫曼编码是:"< huffman(cha,m,k); } 运行截图： 五、总结 经过两个星期的计算机算法设计与分析课程设计，终于顺利完成这次课程设计。通过这次课程设计，收获颇丰。 1、对算法理解更深 通过该课程设计，掌握了计算机算法程序，以及算法的运行原理。通过VC++ 6.0编译器编译算法程序，将书上的算法实现在计算机上，把原来以为很深奥的书本知识变的更为简单，对算法原理有更深的理解。 2、对该算法理论在实践中的应用有深刻的理解 通过把算法程序在计算机上实现，知道和理解了算法在计算机中是怎样执行的，对算法理论在实践中的应用有深刻的理解。 3、激发了学习的积极性 通过该课程设计，全面系统的理解了算法的一般原理和基本实现方法。把死板的课本知识变得生动有趣，激发了学习的积极性。把学过的计算机算法的知识得到了强化，能够把课堂上学的知识通过自己设计的程序表示出来，加深了对算法理论知识的理解。以前对与计算机算法的认识是模糊的，概念上的，现在通过自己动手做实验，从实践上认识了算法的作用，对计算机编程能力也有了进一步的提升。 4、理解了该知识点以及学科之间的融合渗透 本次课程设计程序部分是用C++语言编写的，把《数据结构》《计算机算法设计与分析》《C++程序设计》三门学科联系起来，把各个学科之间的知识融合起来，把各门课程的知识联系起来，对计算机学科知识的认识更加深刻，进一步加深了对这三门课程的认识。 矩阵连乘最佳加括号方式－动态规划算法 一、问题描述 给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,…,n-1。要算出这n个矩阵的连乘积A1A2…A n。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C 的乘积并加括号，即A=(BC)。 例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：（A1（A2（A3A4））），（A1（（A2A3）A4）），（（A1A2）（A3A4）），（（A1（A2A3））A4），（（（A1A2）A3）A4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A是一个p×q矩阵，B是一个q×r矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。 为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵 {A1,A2,A3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A1A2）A3），（A1（A2A3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵{A1,A2,…,A n}（其中矩阵A i的维数为p i-1×p i，i＝1,2,…,n），如何确定计算矩阵连乘积A1A2…A n的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。 穷举搜索法的计算量太大，它不是一个有效的算法，本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。 二、算法思路 动态规划——矩阵连乘的问题 《问题的引出》 看下面一个例子，计算三个矩阵连乘{A1，A2，A3}；维数分别为10*100 , 100*5 , 5*50 按此顺序计算需要的次数（（A1*A2）*A3）:10X100X5+10X5X50=7500次 按此顺序计算需要的次数（A1*（A2*A3））:10X5X50+10X100X50=75000次 所以问题是：如何确定运算顺序，可以使计算量达到最小化。 枚举显然不可，如果枚举的话，相当于一个“完全加括号问题”，次数为卡特兰数,卡特兰数指数增长，必然不行。 《建立递归关系》 子问题状态的建模（很关键）：令m[i][j]表示第i个矩阵至第j个矩阵这段的最优解。 显然如果i=j，则m[i][j]这段中就一个矩阵，需要计算的次数为0； 如果i>j，则m[i][j]=min{m[i][k]+m[k+1][j]+p[i-1]Xp[k]Xp[j]},其中k,在i与j 之间游荡，所以i<=k 所以计算顺序如上右图：相应的计算顺序对应代码为13-15行 m[1][n]即为最终求解，最终的输出想为（（A1（A2 A3））（（A4 A5）A6））的形式，不过没有成功，待思考... 1#include 矩阵连乘问题（动态规划） 一、实验目的与要求 1、明确矩阵连乘的概念。 2、利用动态规划解决矩阵连乘问题。 二、实验题： 问题描述： 给定n个矩阵｛A1,A2,...,An｝，其中Ai与Ai+1是可乘的，i=1，2...，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。 三、实验代码 #include 矩阵连乘问题《算法分析与设计》 设计性实验报告 课程名称：《算法分析与设计》矩阵连乘问题实验题目：长：组员一：成 二：成员成员三：数学与计算机科学系别：系专业班级：指导教师：实验日期： 一、实验目的和要求 实验目的 熟悉动态规划算法设计思想和设计步骤，掌握基 本的程序设计方法，培养学生用计算机解决实际问题的能力。 实验要求 1、根据实验内容，认真编写源程序代码、上机调试程序，书写实验报告。 2、本实验项目考察学生对教材中核心知识的掌握程度和解决实际问题的能力。 3、实验项目可 以采用集中与分散实验相结合的方式进行，学生利用平时实验课时间和课外时间进行 实验，要求在学期末形成完整的项目程序设计报告。 二、实验内容提要 矩阵连乘问题给定n个矩阵{A,A,…,A}， 其中，Ai与Ai+1是可乘的，n21A,A,…,A。由于矩阵乘法满足结n-1。考查这n个矩阵的连乘积i=1,2，…，n12合律，故计算矩阵的连乘积可以有 许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反 复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可 递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=（BC）。 三、实验步骤下面考虑矩阵连乘积的最优计算次序问题的动态规划方法。（1）分析最优解的结构（最优子结构性质）设计求解具体问题的动态规划算法的第一步是刻画该问 题的最优解结构特征。对于矩阵乘积的最优计算次序问题也不例外。首先，为方便起见，降- 1 - 矩阵乘积Ai Ai+1…Aj简记为A[i:j]。 问题描述：给定n个矩阵：A1,A2,...,A n，其中A i与A i+1是可乘的，i=1，2...，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。 问题解析：由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。 完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC) 例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：(A1(A2(A3A4)))，(A1((A2A3)A4))，((A1A2)(A3A4))，((A1(A2A3))A4)，(((A1A2)A3)A4)。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。 看下面一个例子，计算三个矩阵连乘{A1，A2，A3}；维数分别为10*100 , 100*5 , 5*50 按此顺序计算需要的次数 ((A1*A2)*A3):10X100X5+10X5X50=7500次，按此顺序计算需要的次数(A1*(A2*A3)):10*5*50+10*100*50=75000次 所以问题是：如何确定运算顺序，可以使计算量达到最小化。 算法思路： 例：设要计算矩阵连乘乘积A1A2A3A4A5A6，其中各矩阵的维数分别是： A1：30*35; A2：35*15; A3：15*5; A4：5*10; A5：10*20; A6：20*25 递推关系： 设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]。 当i=j时，A[i:j]=A i，因此，m[i][i]=0，i=1,2,…,n 当i 一、问题描述给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要算出这n个矩阵的连乘积A1A2…An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：（A1（A2（A3A4））），（A1（（A2A3）A4）），（（A1A2）（A3A4）），（（A1（A2A3））A4），（（（A1A2）A3）A4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A是一个p×q矩阵，B是一个q×r矩阵，则计算其乘积C=AB 的标准算法中，需要进行pqr次数乘。为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A1,A2,A3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A1A2）A3），（A1（A2A3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵{A1,A2,…,An}（其中矩阵Ai的维数为pi-1×pi，i ＝1,2,…,n），如何确定计算矩阵连乘积A1A2…An的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举搜索法的计算量太大，它不是一个有效的算法，本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。 二、算法思路动态规划算法的基本思想是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，动态规划法经分解得到的子问题往往不是相互独立的，前一子问题的解为后一子问题的解提供有用的信息，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。本实验的算法思路是： 1、计算最优值算法MatrixChain()：建立两张表（即程序中的**m和**s，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n个矩阵相乘的最小运算量；另 目录： 矩阵连乘问题： 1. 描述矩阵连乘问题 2. 分析矩阵连乘问题以及对递归式的推导（1）直接递归思路 （2）备忘录思路 （3）动态规划思路 3. 伪代码的方式描述算法： （1）直接递归算法 （2）备忘录算法 （3）动态规划算法 4. 把算法转换成程序实现的过程及结果（1）直接递归算法程序 （2）备忘录算法程序 （3）动态规划算法程序 1.描述矩阵连乘问题： 给定n 个矩阵{n A A A ?,2,1}，其中i A 和1+i A 是可乘的，i=1,2,…,n-1。考察这n 个矩阵的连乘积n A A A ?,2,1。由于矩阵乘法具有结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说连乘积已完全加括号，则可依次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A 是完全加括号的，则A 可表示为2个完全加括号的矩阵连乘B 和C 的乘积并加括号，即A=（BC ）。 矩阵A 和B 可乘的条件是矩阵A 的列数等于矩阵B 的行数。若A 是一个p ×q 的矩阵，B 是一个q ×r 的矩阵，那么C=A ×B 就是一个p ×r 矩阵。它的计算是三重循环的，计算量是pqr 。如果加括号后矩阵的量是不同的，所以我们的问题就是要讨论如何给连乘的矩阵加括号才能使矩阵的计算量最少。 穷举搜索法：对于n 个矩阵的连乘积，设有不同的计算次序P(n)。由于可以先在第k 个和第k+1个矩阵之间将原矩阵序列分为两个矩阵子序列，k=1,2,...,n-1；然后分别对这两个矩阵子序列完全加括号；最后对所得的结果加括号，得到原矩阵序列的一种完全加括号方式。由此可得P(n)的递归式如下： 1 n=1 P （n ）= ∑-=-1 1 )()(n k k n P k P n>1 解此递归方程可得，P(n)=C(n-1),而C(n)是一个指数增长的函数。因此穷举搜索法不是一个有效的算法。以下将用三种方法来解决矩阵连乘问题的最优加括号方式以及最优解。 2. 分析矩阵连乘问题以及对递归式的推导 将矩阵连乘积j i i A A A ?+,1,简记为A[i:j]。考察计算A[1:n]的最优计算次序。这个问题的一个关键特征是：计算A[1:n]的最优次序包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的。这是因为：定义矩阵A i 的维数为p i-1×p i ,则A[i:k]的计算次数为p i-1×p k ，A[k+1,j]的计算次数为p k ×p j ，而这两个总的矩阵最后相乘时的计算量是固定的，为p i-1×p k ×p j 。所以，矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 （1）、直接递归的思路：记计算A[i:j]，1≤i ≤j ≤n ，所需最少数乘次数为m[i][j],则原问题的最优质为m[1][n]。由分析得知：m[i][j]可以递归的定义为： 0 i=j m[i][j]= }]][1[]][[{min 1j k i j k i p p p j k m k i m -≤≤+++ i 华北电力大学科技学院 实验报告 实验名称矩阵连乘问题 课程名称计算机算法设计与分析 专业班级：软件12K1 学生姓名：吴旭 学号：121909020124 成绩： 指导老师：刘老师实验日期：2014.11.14 一、实验内容 矩阵连乘问题，给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,3…,n-1。考察这n个矩阵的连乘A1,A2,…,A n。 二、主要思想 由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已经完全加括号，则可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归的定义为： (1)单个矩阵是完全加括号的； (2)矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号 的矩阵连乘积B和C的乘积并加括号，即A=(BC)。 运用动态规划法解矩阵连乘积的最优计算次序问题。按以下几个步骤进行 1、分析最优解的结构 设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为A[i:j]。考察计算A[1:n]的最优计算次序。设这个计算次序矩阵在A k和A k+1之间将矩阵链断开，1n,则其相应的完全加括号方式为((A1…A k)(A k+1…A n))。依此次序，先计算A[1:k]和A[k+1:n],然后将计 算结果相乘得到A[1:n]。 2、建立递归关系 设计动态规划算法的第二步是递归定义最优值。对于矩阵连乘积的最优计算次序问题，设计算A[i:j]，1i n，所需的最少数乘次数为m[i][j]，原问题的最优值为m[1][n]。 当i=j时，A[i:j]=A i为单一矩阵，无需计算，因此m[i][i]=0，i=1,2,…n。 当i 动态规划法解矩阵连乘问题 实验内容 给定n个矩阵{A1,A2,….An}，其中Ai与Ai+1是可乘的，i=1,2,3。。。，n-1。我们要计算这n个矩阵的连乘积。由于矩阵乘法满足结合性，故计算矩阵连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则我们可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。 解题思路 将矩阵连乘积A(i)A(i+1)…A(j)简记为A[i:j]，这里 i <= j。考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵A(k)和A(k+1)之间将矩阵链断开，i <= k < j, 则其相应完全加括号方式为(A(i)A(i+1)…A(k)) * (A(k+1)A(k+2)…A(j))。 特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。 设计算A[i:j]，1 <= i <= j <= n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n] 当i = j时，A[i:j]=Ai，因此，m[i,i] = 0，i = 1,2,…,n 当i < j时，m[i,j] = m[i,k] + m[k+1,j] + p(i-1)p(k)p(j)这里A(i)的维数为 p(i-1)*(i)(注：p(i-1)为矩阵A(i)的行数，p(i)为矩阵A[i]的列数) 实验 实验代码 #include 动态规划算法解矩阵连乘问题 一、实验目的 通过上机实验，要求掌握动态规划算法的问题描述、算法设计思想、程序设计和算法复杂性分析等。 二、实验环境 VC6.0 C++，vs2005 三、实验内容 1 用动态规划算法解矩阵连乘问题 （1）问题的描述 给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,…,n-1。要算出这n个矩阵的连乘积A1A2…A n。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的（当然实际上可以不加）； （2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：（A1（A2（A3A4））），（A1（（A2A3）A4）），（（A1A2）（A3A4）），（（A1（A2A3））A4），（（（A1A2）A3）A4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A是一个p×q矩阵，B 是一个q×r矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。 （3）为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A1,A2,A3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A1A2）A3），（A1（A2A3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵{A1,A2,…,A n}（其中矩阵Ai的维数为p i-1×p i，i＝1,2,…,n），如何确定计算矩阵连乘积A1A2…A n的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。正如课堂中所分析，穷举法的计算量太大，它不是一个有效的算法，本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。 （2）算法设计思想 动态规划算法的基本思想是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，动态规划法经分解得到的子问题往往不是相互独立的，前一子问题的解为后一子问题的解提供有用的信息，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。 湖南涉外经济学院计算机科学与技术专业 《算法设计与分析》课程 矩阵连乘备忘录算法 实验报告 班级： 学号： 姓名： 教师： 成绩： 2012年5月 【实验目的】 1 掌握动态规划算法和备忘录方法； 2 利用动态规划备忘录思想实现矩阵连乘； 3 分析实验结果，总结算法的时间和空间复杂度。思考是否能将算法的时间复杂度提高到 O(nlgn) 【系统环境】 Windows 07 平台 【实验工具】 VC++6.0中文企业版 【问题描述】 描述：给定n个矩阵{A1，A2，…，An}，其中Ai与Ai+1可乘的，i=1,2，…，n-1。找出这个n个矩阵的连乘A1A2…An所需相乘的最少次数的方式。 例：矩阵连乘积A1A2A3A4可以有一下五种不同的完全加括号方式： （A1（A2（A3A4））） （A1（（A2A3）A4）） （（A1A2）（A3A4）） （（A1（A2A3））A4） （（（A1A2）A3）A4） 【实验原理】 原理：1、矩阵连乘满足结合律，且不同的结合方式，所需计算的次数不同。 2、利用备忘录方法，用表格保存以解决的子问题答案，降低重复计算，提高效率。 思路：m初始化为0，表示相应的子问题还位被计算。在调用LookupChain时，若m[i][j]>0，则表示其中储存的是所要求子问题的计算结果，直接返回此结果即刻。否则与直接递归算法一样，自顶而下的递归计算，并将计算结果存入m[i][j]后返回。因此，LookupChain总能返回正确的值，但仅在它第一次被调用时计算，以后调用就直接返回计算结果。 方法：用MemorizedMatrixChain函数将已经计算的数据存入表中，用LookupChain函数配合MemorizedMatrixChain函数递归调用计算。 【源程序代码】 #include 福州大学数学与计算机科学学院 《计算机算法设计与分析》上机实验报告（2） i<=k 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 一、选择题 1、衡量一个算法好坏的标准是（ C ）。 （A）运行速度快（B）占用空间少（C）时间复杂度低（D）代码短 2、记号O的定义正确的是（A）。 （A）O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤ cg(n) }；（B）O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤ f(n) }；（C）O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0 有：0 ≤f(n) 实训二 矩阵连乘问题的动态规划算法与实现 一、 设计目的 1） 掌握动态规划算法思想； 2） 掌握矩阵相乘问题的动态规划,得到矩阵相乘问题的最优解； 3） 进一步掌握动态规划法的基本思想和算法设计方法； 二、 设计内容 1． 任务描述 给定n 个矩阵｛A 1,A 2,…,A n ｝，其中A i 与A i +1是可乘的，i=1,2 ,…,n -1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。 A1 A2 A3 A4 A5 A6 30?35 35?15 15?5 5?10 10?20 20?25 2． 主要数据类型与变量 int p[MAX+1]//如任务描述记录30,35,15,5,10,20,25 m[MAX][MAX]//记录存储相乘次数的 s[MAX][MAX]; //记录从哪里断开的才可得到该最优解 int matrixCount;//矩阵个数 3． 算法或程序模块 void matrixChain(int p[21],int n,int m[20][20],int s[20][20]) 功能: 得到矩阵相乘问题的最优解 void Trackback(int i,int j,int s[20][20]) 功能: 按算法MatrixChain 计算出的断点矩阵s 指示的加括号方式输出计算A[i:j] 的最优计算次序。 任务分配 编 码 陈健翔 成绩 综合分数 测 试 朱敏 成绩 三、测试 找不到好的数据,呼呼就拿书上的例子测试吧！我把二维数组m也输出了看了一下,应该是可以的。检查下断开的点,也是正解。 测试多组数据： #include 矩阵连乘实验报告 ————————————————————————————————作者: ————————————————————————————————日期: ? 华北电力大学科技学院 实验报告 实验名称矩阵连乘问题 课程名称计算机算法设计与分析 专业班级：?软件12K１??学生姓名：吴旭 学号：1２1909０２0１２4 成绩: 指导老师: 刘老师?实验日期：2０１４．11.１4 一、实验内容 矩阵连乘问题,给定n个矩阵｛A1，A２,…，A n｝，其中A i与A i+1是可乘的,ｉ=1,2,3…,n-1。考察这n个矩阵的连乘A1,Ａ２,…,A n。 二、主要思想 由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已经完全加括号，则可依此次序反复调用２个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归的定义为: (1)单个矩阵是完全加括号的； (2)矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的 矩阵连乘积Ｂ和Ｃ的乘积并加括号，即Ａ=(BC)。 运用动态规划法解矩阵连乘积的最优计算次序问题。按以下几个步骤进行 1、分析最优解的结构 设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为Ａ［i：j］。考察计算Ａ[1：ｎ]的最优计算次序。设这个计算次序矩阵在Aｋ和A k＋１之间将矩阵链断开,1≤k≤n,则其相应的完全加括号方式为((Ａ …A k)(Ａk+1…A n)）。依此次序，先计算A[１:k]和Ａ[k＋1:ｎ］,然后１ 宁波工程学院电信学院计算机教研室 实验报告 一、实验目的： 通过上级实验，要求掌握动态规划算法的问题描述，算法设计思想，程序设计和算法复杂性分析等。 二、实验环境：VC6.0 三、实验内容： 1、用分治法算法解决最接近点对问题 (1)问题的描述 给定n个矩阵{nAAA ,2,1}，其中iA和1 iA是可乘的，i=1,2,…,n-1。考察这n个矩阵的连乘积nAAA ,2,1。由于矩阵乘法具有结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说连乘积已完全加括号，则可依次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘B和C的乘积并加括号，即A=（BC）。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A 是一个p×q的矩阵，B是一个q×r的矩阵，那么C=A×B就是一个p×r矩阵。它的计算是三重循环的，计算量是pqr。如果加括号后矩阵的量是不同的，所以我们的问题就是要讨论如何给连乘的矩阵加括号才能使矩阵的计算量最少。穷举搜索法：对于n个矩阵的连乘积，设有不同的计算次序P(n)。由于可以先在第k个和第k+1个矩阵之间将原矩阵序列分为两个矩阵子序列，k=1,2,...,n-1；然后分别对这两个矩阵子序列完全加括号；最后对所得的结果加括号，得到原矩阵序列的一种完全加括号方式。 解递归方程可得，P(n)=C(n-1),而C(n)是一个指数增长的函数。因此穷举搜索法不是一个有效的算法。以下将用三种方法来解决矩阵连乘问题的最优加括号方式以及最优解。 (2)算法设计思想 由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。矩阵连乘最佳加括号方式-动态规划算法
矩阵连乘(数据结构)
矩阵连乘问题(动态规划)
矩阵连乘问题算法分析与设计
动态规划矩阵连乘算法
矩阵连乘问题
矩阵连乘问题
矩阵连乘实验报告
动态规划法解矩阵连乘问题
动态规划算法解矩阵连乘问题
矩阵连乘备忘录算法
矩阵连乘算法
算法分析复习题目及答案
算法分析复习题(含答案)
分治法_矩阵连乘问题
动态规划算法解矩阵连乘问题的源代码
矩阵连乘实验报告
矩阵连乘问题
相关主题
文本预览