能量项链问题的解法探讨

摘要： 通过引入程序设计竞赛中的有趣题目，有利于激发学生的学习兴趣，提高学生的实践能力。文章利用动态规划方法的一个典型例子“矩阵连乘问题”解决了一道经典的竞赛题目“能量项链问题”。分析了两个问题的相似性和相异性，得到了能量项链问题的求解方法。

Abstract： Through the introduction of the interesting questions of programming contest， which can help to stimulate the students' interest in learning and to raise the students' practical ability. This paper solves a classic competition topic named energy necklace problem by using a typical example named matrix multiply problem of the dynamic programming method， analyzes the similarity and difference of this two problems， and obtains the solving method of energy necklace problem.

关键词： 动态规划；矩阵连乘问题；能量项链问题

Key words： dynamic programming；matrix multiply problem；energy necklace problem

中图分类号：G42；TP39 文献标识码：A 文章编号：1006-4311（2012）35-0170-02

0 引言

在软件工程专业的算法分析与设计课程中，笔者进行了相关的教学改革，其中最突出的一点就是在讲每种算法设计方法时，都从ACM竞赛或NOI竞赛中挑选有趣的且适合的竞赛题目来引入要讲的这个例子。例如，在讲动态规划算法时，通过赛题“能量项链问题”来引入矩阵连乘问题，通过赛题“回文词的构造”来引入最长公共子序列问题等。通过这些竞赛题目的引入，极大地激发了学生的学习兴趣。本文要讨论的就是如何利用所学的矩阵连乘问题来解决经典的竞赛题目“能量项链问题”。

1 问题描述

1.1 矩阵连乘问题 几乎在任何一本关于算法分析与设计课程的教材中，在介绍动态规划算法时，都无一例外的会讲授矩阵连乘问题，该问题是能用利用动态规划方法解决的典型问题。该问题是说：给定n个矩阵A1，A2，…，An，其中矩阵Ai（1≤i≤n）的维数为pi×pi+1，于是相邻的两个矩阵就是可以相乘的。考虑这n个矩阵的连乘积A1A2…An，由于矩阵乘法满足结合律，所以求解这个矩阵连乘积时可以有许多不同的计算次序，每种计算次序都对应一个乘法次数。那么矩阵连乘问题就是要确定一个矩阵连乘积的一种最优计算次序，使得计算一个矩阵连乘积时，所需要的乘法次数最少。

假设用二维数组m来保存问题的最优值，数组元素m[i][j]保存的是求解矩阵连乘积AiAi+1…Aj-1Aj时所需的最少乘法次数。则根据最优子结构性质，容易建立m[i][j]所满足的递推关系式如下。

（1）i=j m[i][j]=0

（2）i

根据递推关系式容易给出求解最小乘法次数的动态规划算法，如下所示。

int p[100]，m[100][100]；

void matrix_min（int n）

{ for（int i=1；i

m[i][i]=0；

for（int r=2；r

for（int i=1；i

{ int j=i+r-1；

m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1]；

for（int k=i+1；k

{ int min=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1]；

if （minm[i][j]）

m[i][j]=min；

}

}

}

调用该算法可求出n个矩阵相乘时所需的最少乘法次数，若要求n个矩阵相乘时所需的最大乘法次数则只需将matrix_min算法中if语句条件中的“”即可，为了便于描述，将求n个矩阵相乘时所需的最大乘法次数的算法命名为matrix_max算法。

1.2 能量项链问题 在NOIP2006提高组复赛试题中有一道题目，叫做“能量项链问题”，题目的大致含义是：在一串能量项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，这两颗珠子才能聚合成一颗珠子，同时释放出能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则这两颗能量珠聚合后释放的能量为m×r×n，新产生的珠子的头标记为m，尾标记为n。

显然，N颗珠子聚合成一颗珠子时会有许多不同的聚合次序，不同的聚合顺序得到的总能量是不同的，能量项链问题就是要确定N颗珠子聚合时的一种最优聚合次序，使得按照这种次序将N颗珠子聚合成一颗珠子时，释放出的总能量最大。

例如：设N=4，4颗珠子的头标记与尾标记依次为（2，3），（3，5），（5，10），（10，2）。则这4颗珠子的一种最优聚合次序及释放出的最大能量值如下。

（（4？茌1）？茌2）？茌3）=10×2×3+10×3×5+10×5×10=710。

符号？茌表示聚合操作。

2 矩阵连乘问题与能量项链问题的相似性与相异性

由以上两个问题的描述可知，它们之间有许多相似之处，其相似性可归纳为以下五点。

①矩阵和珠子非常相似，每个矩阵都有行数和列数，每个珠子都有头标记和尾标记；②对于相邻的两个矩阵来说，前一个矩阵的列等于后一个矩阵的行，对于相邻的两个珠子来说，前一个珠子的尾标记等于后一个珠子的头标记；③相邻的两个矩阵相乘时所需的乘法次数为这两个矩阵的三个维数的乘积，相邻的两个珠子聚合时所产生的能量为这两个珠子的三个标记的乘积；④两个矩阵相乘后得到一个矩阵，这个矩阵的行数为第一个矩阵的行，这个矩阵的列数为第二个矩阵的列，中间相同的维数抵消了。两个珠子聚合后得到一个珠子，这个珠子的头标记为第一个珠子的头标记，这个珠子的尾标记为第二个珠子的尾标记，中间相同的标记抵消了；⑤n个矩阵相乘时，一种计算次序所对应的乘法次数是每一次相乘时所需的乘法次数之和，n个珠子聚合时，一种聚合次序所对应的能量值是每一次聚合时所产生的能量之和。

当然，两个问题之间也有区别，主要有两点。①在矩阵连乘问题中，第n个矩阵和第1个矩阵是不相邻的，而在能量项链问题中，第n个珠子和第1个珠子是相邻的，第n个珠子的尾标记一定要等于第1个珠子的头标记，这两个珠子是可以进行聚合操作的；②在矩阵连乘问题中，是要确定n个矩阵相乘的一种最优计算次序，使得所需要的乘法次数最少。而在能量项链问题中，是要确定n个珠子聚合时的一种最优聚合次序，使得释放的总能量值最大。

3 能量项链问题的解法探讨

鉴于以上分析，能量项链问题其实就是一个特殊的矩阵连乘问题，可将一个珠子看成是一个矩阵，将n个珠子构成的能量项链看成是由n个矩阵构成的环形矩阵连乘积，只不过在这个环形矩阵连乘积中，第n个矩阵的列数一定要等于第1个矩阵的行数。两个珠子聚合后产生的能量值就是它们对应的两个矩阵相乘时所需的乘法次数，n个珠子聚合成一个珠子时产生的总能量值就是这n个矩阵相乘后得到一个矩阵时所需的总的乘法次数，要确定n个珠子聚合时的一种最优聚合次序，使得释放的总能量值最大。也就是要确定这n个矩阵构成的环形矩阵连乘问题的一种最优计算次序，使得所需的乘法次数达到最大。

在n个矩阵直线相乘时，第n个矩阵和第1个矩阵是不相邻的，即这两个矩阵是不能相乘的。而当这n个矩阵环形相乘时，第n个矩阵和第1个矩阵是相邻的，这两个矩阵是可以相乘的，这种相邻性的改变使问题变得复杂了。在n个矩阵直线相乘时，长度为n的矩阵连乘积只有一种，就是A1A2…An，而当n个矩阵环形相乘时，长度为n的矩阵连乘积就有n种，分别是：A1A2…An-1An，A2A3…AnA1，依此类推，最后一种是AnA1…An-2An-1。其实要表示出这n种情况，可将n个矩阵构成的圆环在矩阵An和A1之间断开，拉成一条直线，然后在矩阵An的后面添加上n-1个矩阵，也就是添加上A1A2…An-2An-1，这样就形成了一个长度为2n-1的直线矩阵链，显然在这个长度为2n-1的直线矩阵链中，上述n种情况都可以表示出来。

若用An+i来表示新添加的第i个矩阵，这里1≤i≤n-1，则有An+i=Ai。对于这个长度为2n-1的直线矩阵连乘问题来说，上述n种直线相乘的情况就是这个问题的n个子问题，因此，只需要利用matrix_max算法求长度为2n-1的直线矩阵连乘问题的最大乘法次数即可，在以自底向上方式计算它的最大乘法次数时，所有长度为n的子矩阵连乘积所需的最大乘法次数都已经求完了，共有n个，由matrix_max算法的思想可知，长度为n的子矩阵连乘积所需的最大乘法次数可表示为m[i][i+n-1]，这里1≤i≤n，最终这n个m[i][i+n-1]中的最大者就是n个矩阵环形相乘时所需的最大乘法次数。

根据上述方法求解环形矩阵连乘问题最优值的步骤可归纳为三步。

①扩充操作，添加n-1个矩阵，从而将长度为n的环形矩阵连乘问题转化为长度为2n-1的直线矩阵连乘问题；②调用matrix_max算法求长度为2n-1的直线矩阵连乘问题的最优值；③求n个m[i][i+n-1]中的最大者。

根据上述思想，其求解算法如下所示。

int circlematrix（int n）

{ int i， max=0；

for（i=2；i

p[n+i]=p[i]；

matrix_max（2*n-1）；

for（i=1；i

if（m[i][i+n-1]>max）

max=m[i][i+n-1]；

return max；

}

4 结论

本文利用“矩阵连乘问题”解决了一道经典的竞赛题目“能量项链问题”，在授课程过程中，笔者曾以一个学生为例引入了这道竞赛题目，课堂效果非常好。通过竞赛题目的引入和讲解，有利于激发学生的学习兴趣，对算法分析与设计课程不再有畏难心理，提高学生的算法设计能力，并有利于开展素质教育活动，积极指导学生参加学科竞赛。

参考文献：

[1]潘金贵，顾铁成等译.算法导论[M].北京：机械工业出版社，2007：197-202.

[2]王晓东.算法设计与分析习题解答[M].北京：清华大学出版社，2006：89-91.

[3]霍红卫.算法设计与分析[M].西安：西安电子科技大学出版社，2005：54-60.