算法分析与设计课程中矩阵连乘问题的教学探讨

摘要：文章介绍了算法分析与设计课程中矩阵连乘问题的动态规划算法，利用该算法解决了两道经典竞赛题目，即能量项链问题和石子合并问题。对于能量项链问题，其求解思想是将其转换为一个环形矩阵连乘问题，然后求解这个环形矩阵连乘积所需的最大乘法次数。对于石子合并问题，分析出它与矩阵连乘问题的相似性，从而借鉴矩阵连乘问题的求解方法实现求解。通过这两个问题的求解，有助于学生举一反三，启发学生思维，以学致用，提高问题求解能力。

关键词：矩阵连乘问题；能量项链问题；石子合并问题

中图分类号：G642.0 文献标志码：A 文章编号：1674-9324（2016）18-0206-03

在算法分析与设计课程中，矩阵连乘问题[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]所满足的递推关系式如下。

}

}

二、利用矩阵连乘问题求解能量项链问题

（一）能量项链问题描述

能量项链问题[3]是NOIP2006提高组复赛试题中的一道题目，该问题描述如下。在火星上，每个火星人都随身佩带着一串能量项链。在项链上有N颗能量珠，能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。对于相邻的两颗珠子而言，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是火星人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则这两颗能量珠聚合后释放的能量为m×r×n，新产生的珠子的头标记为m，尾标记为n。

例如：设N=4，4颗珠子的头标记与尾标记依次为（2，3），（3，5），（5，10），（10，2）。用记号表示两颗珠子的聚合操作，（jk）表示第j，k两颗珠子聚合后所释放的能量，则第4、1两颗珠子聚合后释放的能量为：（41）=10×2×3=60，这两颗能量珠聚合后得到的新能量珠的头尾标记为（10，3）。4颗珠子聚合成一颗珠子时有许多不同的聚合次序，每种聚合次序对应了一个能量值，4颗珠子聚合时的一种最优聚合顺序以及所释放的最大能量为：

（（41）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的直线矩阵连乘积所需的最大乘法次数了。

根据上述思想，求解环形矩阵连乘问题的最大乘法次数的枚举算法如下所示。

三、结论

文章介绍了算法分析与设计课程中矩阵连乘问题的动态规划算法，然后重点讨论了它的两个应用，即应用矩阵连乘问题求解能量项链问题和石子合并问题，并给出了相关的求解算法。笔者在授课过程中，通过讲解这两个应用，使得学生对矩阵连乘问题有了更深刻的理解，有助于学生学以致用，举一反三，收到了非常好的效果。

参考文献：

[1]沈孝钧.计算机算法基础[M].北京：机械工业出版社，2014：63-68.

[2]王晓东.算法设计与分析[M].北京：清华大学出版社，2006：62-67.

[3]刘文强，周波，顾泽元等.能量项链问题的解法探讨[J].价值工程，2012，31（295）：170-171.