毕业论文网
本论文是一篇免费优秀的关于算法分析论文范文资料，可用于相关论文写作参考。
算法分析和设计课程中矩阵连乘问题的教学
刘,周波,桑海涛,顾泽元,韩娜
（黑龙江科技大学计算机与信息工程学院,黑龙江哈尔滨150022）
摘 要：文章介绍了算法分析与设计课程中矩阵连乘问题的动态规划算法,利用该算法解决了两道经典竞赛题目,即能量项链问题和石子合并问题.对于能量项链问题,其求解思想是将其转换为一个环形矩阵连乘问题,然后求解这个环形矩阵连乘积所需的最大乘法次数.对于石子合并问题,分析出它与矩阵连乘问题的相似性,从而借鉴矩阵连乘问题的求解方法实现求解.通过这两个问题的求解,有助于学生举一反三,启发学生思维,以学致用,提高问题求解能力.
关键词：矩阵连乘问题；能量项链问题；石子合并问题
中图分类号：G642.0 文献标志码：A 文章编号：1674-9324（2016）18-0206-03
基金项目：本文系2014年黑龙江科技大学教学研究项目“基于学科竞赛活动的算法分析与设计课程教学改革探索”（项目编号：JY14-98）；2014年黑龙江省高等教育教学改革项目“工程能力为目标的程序设计课程体系研究”（项目编号：JG2014010997）；2013年黑龙江省教育科学十二五规划课题“《网络安全》课程网络攻防实践教学平台开发”（项目编号：GBD1213039）的研究成果
作者简介：刘（1980-）,男（汉族）,黑龙江省巴彦人,硕士研究生,讲师,研究方向：信息融合估计理论,鲁棒Kalman滤波.
在算法分析与设计课程中,矩阵连乘问题[1-2]是一个可用动态规划方法求解的经典最优化问题,利用该问题可以有效地求解许多实际问题.
该问题描述为：给定n个矩阵A1,A2,…,An,其中矩阵Ai （1≤i ≤n） 的维数为pi ×pi+1,即矩阵A1的维数为p1×p2,矩阵A2的维数为p2×p3,依此类推,矩阵An的维数为pn×pn+1.考虑这n个矩阵的连乘积A1A2…An,由于矩阵乘法满足结合律,所以求解这个矩阵连乘积时可以有许多不同的计算次序,每种计算次序都有一个计算量,这里所说的计算量是指按照某种计算次序来计算一个矩阵连乘积时所需的乘法次数.那么矩阵连乘问题就是要确定一个矩阵连乘积的一种最优计算次序,使得按照这种最优计算次序来计算一个矩阵连乘积时,所需要的乘法次数最少.
一、矩阵连乘问题的动态规划算法
用记号A[i：j]来表示矩阵连乘积AiAi+1…Aj-1Aj.定义一个二维数组m来保存求解一个矩阵连乘积时所需的最少乘法次数,数组元素m[i][j]保存的是求解矩阵连乘积A[i：j]时所需的最少乘法次数.根据最优子结构性质,容易建立m[i][j]所满足的递推关系式如下.
（1）i等于j时m[i][j]等于0.
（2）i<j时m［i］［j ］等于 min
i≤k＜j
{m［i］［k ］+m［k+1］［j ］+pipk+1
pj+1}
根据m[i][j]所满足的递推关系式可以自底向上的方式计算出m[i][j],求解m[i][j]的动态规划算法如下.
int p[100],m[100][100]； //数组p用来存储n个矩阵的n+1个不同的维数
void matrix（int n） //matrix算法求解A1A2…An所需的最少乘法次数
{ for（int i等于1；i<等于n；i++） m[i][i]等于0；
for（int r等于2；r<等于n；r++） //r为矩阵连乘积中矩阵的个数
for（int i等于1；i<等于n-r+1；i++） //i为长度为r的矩阵链中首矩阵的所有可能编号
{ int j等于i+r-1； //j为长度为r的矩阵链中尾矩阵的所有可能编号
m[i][j]等于m[i+1][j]+ p[i]*p[i+1]*p[j+1]； //断开位置k等于i的情况
for（int k等于i+1；k<j；k++） //枚举断开位置k的其他取值
{ int min等于m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1]；
if（min<m[i][j]） m[i][j]等于min；
}
}
}
二、利用矩阵连乘问题求解能量项链问题
(一)能量项链问题描述
能量项链问题[3]是NOIP2006提高组复赛试题中的一道题目,该问题描述如下.在火星上,每个火星人都随身佩带着一串能量项链.在项链上有N颗能量珠,能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数.对于相邻的两颗珠子而言,前一颗珠子的尾标记一定等于后一颗珠子的头标记.因为只有这样,通过吸盘（吸盘是火星人吸收能量的一种器官）的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量.如果前一颗能量珠的头标记为m,尾标记为r,后一颗能量珠的头标记为r,尾标记为n,则这两颗能量珠聚合后释放的能量为m×r×n,新产生的珠子的头标记为m,尾标记为n.
例如：设N等于4,4颗珠子的头标记与尾标记依次为（2,3）,（3,5）,（5,10）,（10,2）.用记号⊕表示两颗珠子的聚合操作,（j⊕k）表示第j,k两颗珠子聚合后所释放的能量,则第4、1两颗珠子聚合后释放的能量为：（4⊕1）等于10×2×3等于60,这两颗能量珠聚合后得到的新能量珠的头尾标记为（10,3）.4颗珠子聚合成一颗珠子时有许多不同的聚合次序,每种聚合次序对应了一个能量值,4颗珠子聚合时的一种最优聚合顺序以及所释放的最大能量为：
（（4⊕1）⊕2）⊕3）等于10×2×3+10×3×5+10×5×10等于710.
对于由n颗珠子构成的能量项链,已知每颗珠子的首尾标记,要求确定这n颗珠子聚合成一颗珠子的一种最优聚合次序,使得释放的总能量最大,最终输出最大能量值.
(二)能量项链问题求解算法
由能量项链问题描述可看出,该问题与矩阵连乘问题十分相似,可看成一个由n个矩阵构成的环形矩阵连乘问题,就是要确定这n个矩阵构成的环形矩阵连乘积的一种最优计算次序,使得按照这种最优计算次序来计算这个环形矩阵连乘积时,所需的乘法次数达到最大.
将matrix算法的if语句中的“<”改成“>”,即可实现求解一个直线矩阵连乘积的最大乘法次数了.
在文献[3]中采用扩充方法求解了环形矩阵连乘问题,本文则采用枚举法来直接求解环形矩阵连乘问题,更直接也更容易理解.
在n个矩阵直线相乘时,第n个矩阵和第1个矩阵是不相邻的,即这两个矩阵是不能相乘的.而当这n个矩阵环形相乘时,第n个矩阵和第1个矩阵是相邻的,这两个矩阵是可以相乘的,这种相邻性的改变使问题变得复杂了.在n个矩阵直线相乘时,长度为n的矩阵连乘积只有几种啊,只有一种,就是A1A2…An,而当n个矩阵环形相乘时,长度为n的矩阵连乘积又有几种呢？这时就有n种,分别是：A1A2A3…An-2An-1An,A2A3A4…An-1AnA1,A3A4A5…AnA1A2,依此类推,最后一种是AnA1A2…An-3An-2An-1.因此,可以采用枚举法来求n个矩阵构成的环形矩阵连乘问题,思路就是枚举n个矩阵环形相乘时所对应的每一种长度为n的n个矩阵直线相乘的情况,对每一种n个矩阵直线相乘时的矩阵连乘积计算它的最大乘法次数,能求出n个最大乘法次数,则n个矩阵环形相乘时的最大乘法次数就是这n个最大乘法次数中的最大者.
在算法中,定义一个辅助数组r ,在主函数中按照A1A2A3…An-2An-1An的顺序向r[1],r[2],r[3],...,r[n],r[n+1]中输入这n个矩阵的n+1个维数.而用数组p来保存当前考察的这个直线相乘的情况所对应的n个矩阵的n+1个维数.当前考察的直线相乘的情况可以统一表示为AiAi+1Ai+2…AnA1A2…Ai-3Ai-2Ai-1,这里,1≤i≤n.这时,可以将这种直线相乘的情况看成是由两部分组成的,第一部分是AiAi+1Ai+2…An,第二部分是A1A2…Ai-3Ai-2Ai-1,因此可以将这两部分对应的r数组值分别赋值到数组p中,首先将第一部分AiAi+1Ai+2…An中各个矩阵对应的r数组值赋值到数组p中,而AiAi+1Ai+2…An这些矩阵对应的r数组值就是r[i],r[i+1],r[i+2],...,r[n],因此只需将r[i],r[i+1],r[i+2],...,r[n]赋值到数组p的前面若干个单元中.然后再将第二部分A1A2…Ai-3Ai-2Ai-1中各个矩阵对应的r数组值赋值到数组p中,而A1A2…Ai-3Ai-2Ai-1这些矩阵对应的r数组值有i个,分别为r[1],r[2],r[3],...,r[i-1]和r[i],其中r[1],r[2],r[3],...,r[i-1]表示这i-1个矩阵的行数,r[i]表示最后一个矩阵Ai-1的列数.因此只需将r[1],r[2],r[3],...,r[i-1]和r[i]赋值到数组p的后面若干个单元中.得到了数组p,就可以调用matrix算法来求解当前这个长度为n的直线矩阵连乘积所需的最大乘法次数了.
根据上述思想,求解环形矩阵连乘问题的最大乘法次数的枚举算法如下所示.
int circlematrix（int n,int r[]）
{ int i等于1,j,k,max等于0；
while（i<等于n）
{ k等于1；
for（j等于i；j<等于n；j++）{ p[k]等于r[j]；k++；}
for（j等于1；j<等于i；j++）{ p[k]等于r[j]；k++；}
matrix（n）；
if（m[1][n]>max）max等于m[1][n]；
i++；
}
return max；
}
(三)利用矩阵连乘问题求解石子合并问题
1.石子合并问题描述.该问题描述如下.规定每次只能选相邻的两堆合并成一堆,并将新合并的这堆石子的石子数记为该次合并的得分,将n堆石子合并成一堆的总得分定义为每一次合并的得分之和.石子合并问题是指确定将n堆石子合并为一堆时的一种最优计算次序,使得将n堆石子合并成一堆时,总得分最小.
例如：设有3堆石子排成一行,这3堆石子从左到右依次编号为1,2,3,这3堆石子的石子数分别是A1等于2,A2等于4,A3等于6,则这3堆石子的合并有两种方式,第一种方式是：（（A1 A2）A3）,显然在这种方式下,合并的得分为：6+12等于18；第二种方式为：（A1（A2A3））,显然在这种方式下,合并的得分为：10+12等于22.因此,对于这个问题来说,其合并的最小得分为18,其最优合并方式为（A1（A2 A3））.
2.石子合并问题求解算法.石子合并问题与矩阵连乘问题十分相似.首先,矩阵连乘问题中只有相邻的两个矩阵可以相乘,两个矩阵相乘时所需的乘法次数为两个矩阵的三个维数的乘积.而石子合并问题中只有相邻的两堆石子可以合并,两堆石子合并时的得分为两堆石子的石子总数.矩阵连乘问题是要确定n个矩阵相乘时的一种最优计算次序使得总的乘法次数最少,而石子合并问题是要确定n堆石子合并为一堆时的一种最优计算次序,使得合并的总得分最少.两个问题的区别在于乘法次数与得分的计算方式不同.可以借鉴矩阵连乘问题的求解算法来求解石子合并问题.
用A[i：j]来表示合并AiAi+1…Aj-1Aj的过程,用m[i][j]表示合并A[i：j]这j-i+1堆石子所得的最小得分,下面给出m[i][j]所满足的递归关系式.
（1）i等于j
当i等于j时,显然这时要合并的石子只有一堆,不需要进行任何操作,因此这是m[i][j]等于0.
（2）i<j
设最优合并方式所对应的断开位置是在Ak和Ak+1之间断开,显然i≤k<j.则A[i：j]的合并方式可表示为A[i：j]等于（（A[i：k]）（A[k+1：j]））.由最优子结构性质可知,左右两个子问题即A[i：k]和A[k+1：j]的合并方式也是最优的,即其合并的得分也是最小的.因此合并A[i：j]的最小得分可表示为三个部分的和,即为m[i][j]等于m[i][k]+m[k+1][j]+jt等于i ΣAt,其中m[i][k]为合并A[i：k]的最小得分,m[k+1][j]为合并A[k+1：j]的最小得分,而jt等于i ΣAt则是将A[i：k]和A[k+1：j]这两大堆石子合并为一堆的得分,显然这个得分应为这两大堆的石子数的和,因此得到上式.上式是在假设A[i：j]的最优合并方式是在Ak和Ak+1之间断开时得到的,因此要得到m[i][j],关键是确定k,显然i≤k<j,即k只有j-i种可能,则k一定是这j-i种可能中使这三项的和达到最小的那一个,因此有：
根据m[i][j]所满足的递推关系式可以自底向上的方式计算出m[i][j],求解m[i][j]的动态规划算法如下.
int a[100],m[100][100]；
void stonemerge（int n）
{ for（int i等于1；i<等于n；i++） mi[][i]等于0；
for（int i等于2；i<等于n；i++） a[i]等于a[i]+a[i-1]；
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]+a[j]-a[i-1]；
for（int k等于i+1；k<j；k++）
{ int min等于m[i][k]+m[k+1][j]+a[j]-a[i-1]；
if（min<m[i][j]） m[i][j]等于min；
}
}
}
三、结论
文章介绍了算法分析与设计课程中矩阵连乘问题的动态规划算法,然后重点讨论了它的两个应用,即应用矩阵连乘问题求解能量项链问题和石子合并问题,并给出了相关的求解算法.笔者在授课过程中,通过讲解这两个应用,使得学生对矩阵连乘问题有了更深刻的理解,有助于学生学以致用,举一反三,收到了非常好的效果.
算法分析论文范文结:
关于本文可作为相关专业算法分析论文写作研究的大学硕士与本科毕业论文算法分析论文开题报告范文和职称论文参考文献资料。