算法分析與設(shè)計(jì)課程中矩陣連乘問題的教學(xué)探討

劉文強(qiáng) 周波 桑海濤 顧澤元 韓娜

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

關(guān)鍵詞：矩陣連乘問題；能量項(xiàng)鏈問題；石子合并問題

中圖分類號：G642.0 文獻(xiàn)標(biāo)志碼：A 文章編號：1674-9324（2016）18-0206-03

在算法分析與設(shè)計(jì)課程中，矩陣連乘問題[1-2]是一個(gè)可用動態(tài)規(guī)劃方法求解的經(jīng)典最優(yōu)化問題，利用該問題可以有效地求解許多實(shí)際問題。

該問題描述為：給定n個(gè)矩陣A1，A2，…，An，其中矩陣Ai（1≤i≤n）的維數(shù)為pi×pi+1，即矩陣A1的維數(shù)為p1×p2，矩陣A2的維數(shù)為p2×p3，依此類推，矩陣An的維數(shù)為pn×pn+1。考慮這n個(gè)矩陣的連乘積A1A2…An，由于矩陣乘法滿足結(jié)合律，所以求解這個(gè)矩陣連乘積時(shí)可以有許多不同的計(jì)算次序，每種計(jì)算次序都有一個(gè)計(jì)算量，這里所說的計(jì)算量是指按照某種計(jì)算次序來計(jì)算一個(gè)矩陣連乘積時(shí)所需的乘法次數(shù)。那么矩陣連乘問題就是要確定一個(gè)矩陣連乘積的一種最優(yōu)計(jì)算次序，使得按照這種最優(yōu)計(jì)算次序來計(jì)算一個(gè)矩陣連乘積時(shí)，所需要的乘法次數(shù)最少。

一、矩陣連乘問題的動態(tài)規(guī)劃算法

用記號A[i：j]來表示矩陣連乘積AiAi+1…Aj-1Aj。定義一個(gè)二維數(shù)組m來保存求解一個(gè)矩陣連乘積時(shí)所需的最少乘法次數(shù)，數(shù)組元素m[i][j]保存的是求解矩陣連乘積A[i：j]時(shí)所需的最少乘法次數(shù)。根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)，容易建立m[i][j]所滿足的遞推關(guān)系式如下。

}

}

二、利用矩陣連乘問題求解能量項(xiàng)鏈問題

（一）能量項(xiàng)鏈問題描述

能量項(xiàng)鏈問題[3]是NOIP2006提高組復(fù)賽試題中的一道題目，該問題描述如下。在火星上，每個(gè)火星人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有N顆能量珠，能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對應(yīng)著某個(gè)正整數(shù)。對于相鄰的兩顆珠子而言，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因?yàn)橹挥羞@樣，通過吸盤（吸盤是火星人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時(shí)釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標(biāo)記為m，尾標(biāo)記為r，后一顆能量珠的頭標(biāo)記為r，尾標(biāo)記為n，則這兩顆能量珠聚合后釋放的能量為m×r×n，新產(chǎn)生的珠子的頭標(biāo)記為m，尾標(biāo)記為n。

例如：設(shè)N=4，4顆珠子的頭標(biāo)記與尾標(biāo)記依次為（2，3），（3，5），（5，10），（10，2）。用記號⊕表示兩顆珠子的聚合操作，（j⊕k）表示第j，k兩顆珠子聚合后所釋放的能量，則第4、1兩顆珠子聚合后釋放的能量為：（4⊕1）=10×2×3=60，這兩顆能量珠聚合后得到的新能量珠的頭尾標(biāo)記為（10，3）。4顆珠子聚合成一顆珠子時(shí)有許多不同的聚合次序，每種聚合次序?qū)?yīng)了一個(gè)能量值，4顆珠子聚合時(shí)的一種最優(yōu)聚合順序以及所釋放的最大能量為：

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

對于由n顆珠子構(gòu)成的能量項(xiàng)鏈，已知每顆珠子的首尾標(biāo)記，要求確定這n顆珠子聚合成一顆珠子的一種最優(yōu)聚合次序，使得釋放的總能量最大，最終輸出最大能量值。

（二）能量項(xiàng)鏈問題求解算法

由能量項(xiàng)鏈問題描述可看出，該問題與矩陣連乘問題十分相似，可看成一個(gè)由n個(gè)矩陣構(gòu)成的環(huán)形矩陣連乘問題，就是要確定這n個(gè)矩陣構(gòu)成的環(huán)形矩陣連乘積的一種最優(yōu)計(jì)算次序，使得按照這種最優(yōu)計(jì)算次序來計(jì)算這個(gè)環(huán)形矩陣連乘積時(shí)，所需的乘法次數(shù)達(dá)到最大。

將matrix算法的if語句中的“<”改成“>”，即可實(shí)現(xiàn)求解一個(gè)直線矩陣連乘積的最大乘法次數(shù)了。

在文獻(xiàn)[3]中采用擴(kuò)充方法求解了環(huán)形矩陣連乘問題，本文則采用枚舉法來直接求解環(huán)形矩陣連乘問題，更直接也更容易理解。

在n個(gè)矩陣直線相乘時(shí)，第n個(gè)矩陣和第1個(gè)矩陣是不相鄰的，即這兩個(gè)矩陣是不能相乘的。而當(dāng)這n個(gè)矩陣環(huán)形相乘時(shí)，第n個(gè)矩陣和第1個(gè)矩陣是相鄰的，這兩個(gè)矩陣是可以相乘的，這種相鄰性的改變使問題變得復(fù)雜了。在n個(gè)矩陣直線相乘時(shí)，長度為n的矩陣連乘積只有幾種啊，只有一種，就是A1A2…An，而當(dāng)n個(gè)矩陣環(huán)形相乘時(shí)，長度為n的矩陣連乘積又有幾種呢？這時(shí)就有n種，分別是：A1A2A3…An-2An-1An，A2A3A4…An-1AnA1，A3A4A5…AnA1A2，依此類推，最后一種是AnA1A2…An-3An-2An-1。因此，可以采用枚舉法來求n個(gè)矩陣構(gòu)成的環(huán)形矩陣連乘問題，思路就是枚舉n個(gè)矩陣環(huán)形相乘時(shí)所對應(yīng)的每一種長度為n的n個(gè)矩陣直線相乘的情況，對每一種n個(gè)矩陣直線相乘時(shí)的矩陣連乘積計(jì)算它的最大乘法次數(shù)，能求出n個(gè)最大乘法次數(shù)，則n個(gè)矩陣環(huán)形相乘時(shí)的最大乘法次數(shù)就是這n個(gè)最大乘法次數(shù)中的最大者。

在算法中，定義一個(gè)輔助數(shù)組r，在主函數(shù)中按照A1A2A3…An-2An-1An的順序向r[1]，r[2]，r[3]，...，r[n]，r[n+1]中輸入這n個(gè)矩陣的n+1個(gè)維數(shù)。而用數(shù)組p來保存當(dāng)前考察的這個(gè)直線相乘的情況所對應(yīng)的n個(gè)矩陣的n+1個(gè)維數(shù)。當(dāng)前考察的直線相乘的情況可以統(tǒng)一表示為AiAi+1Ai+2…AnA1A2…Ai-3Ai-2Ai-1，這里，1≤i≤n。這時(shí)，可以將這種直線相乘的情況看成是由兩部分組成的，第一部分是AiAi+1Ai+2…An，第二部分是A1A2…Ai-3Ai-2Ai-1，因此可以將這兩部分對應(yīng)的r數(shù)組值分別賦值到數(shù)組p中，首先將第一部分AiAi+1Ai+2…An中各個(gè)矩陣對應(yīng)的r數(shù)組值賦值到數(shù)組p中，而AiAi+1Ai+2…An這些矩陣對應(yīng)的r數(shù)組值就是r[i]，r[i+1]，r[i+2]，...，r[n]，因此只需將r[i]，r[i+1]，r[i+2]，...，r[n]賦值到數(shù)組p的前面若干個(gè)單元中。然后再將第二部分A1A2…Ai-3Ai-2Ai-1中各個(gè)矩陣對應(yīng)的r數(shù)組值賦值到數(shù)組p中，而A1A2…Ai-3Ai-2Ai-1這些矩陣對應(yīng)的r數(shù)組值有i個(gè)，分別為r[1]，r[2]，r[3]，...，r[i-1]和r[i]，其中r[1]，r[2]，r[3]，...，r[i-1]表示這i-1個(gè)矩陣的行數(shù)，r[i]表示最后一個(gè)矩陣Ai-1的列數(shù)。因此只需將r[1]，r[2]，r[3]，...，r[i-1]和r[i]賦值到數(shù)組p的后面若干個(gè)單元中。得到了數(shù)組p，就可以調(diào)用matrix算法來求解當(dāng)前這個(gè)長度為n的直線矩陣連乘積所需的最大乘法次數(shù)了。

根據(jù)上述思想，求解環(huán)形矩陣連乘問題的最大乘法次數(shù)的枚舉算法如下所示。

三、結(jié)論

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

參考文獻(xiàn)：

[1]沈孝鈞.計(jì)算機(jī)算法基礎(chǔ)[M].北京：機(jī)械工業(yè)出版社，2014：63-68.

[2]王曉東.算法設(shè)計(jì)與分析[M].北京：清華大學(xué)出版社，2006：62-67.

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