算法分析與設計課程中矩陣連乘問題的教學探討

劉文強 周波 桑海濤 顧澤元 韓娜

摘要：文章介紹了算法分析與設計課程中矩陣連乘問題的動態規劃算法，利用該算法解決了兩道經典競賽題目，即能量項鏈問題和石子合并問題。對于能量項鏈問題，其求解思想是將其轉換為一個環形矩陣連乘問題，然后求解這個環形矩陣連乘積所需的最大乘法次數。對于石子合并問題，分析出它與矩陣連乘問題的相似性，從而借鑒矩陣連乘問題的求解方法實現求解。通過這兩個問題的求解，有助于學生舉一反三，啟發學生思維，以學致用，提高問題求解能力。

關鍵詞：矩陣連乘問題；能量項鏈問題；石子合并問題

中圖分類號：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）。用記號⊕表示兩顆珠子的聚合操作，（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的直線矩陣連乘積所需的最大乘法次數了。

根據上述思想，求解環形矩陣連乘問題的最大乘法次數的枚舉算法如下所示。

三、結論

文章介紹了算法分析與設計課程中矩陣連乘問題的動態規劃算法，然后重點討論了它的兩個應用，即應用矩陣連乘問題求解能量項鏈問題和石子合并問題，并給出了相關的求解算法。筆者在授課過程中，通過講解這兩個應用，使得學生對矩陣連乘問題有了更深刻的理解，有助于學生學以致用，舉一反三，收到了非常好的效果。

參考文獻：

[1]沈孝鈞.計算機算法基礎[M].北京：機械工業出版社，2014：63-68.

[2]王曉東.算法設計與分析[M].北京：清華大學出版社，2006：62-67.

[3]劉文強，周波，顧澤元等.能量項鏈問題的解法探討[J].價值工程，2012，31（295）：170-171.