矩陣鏈乘積的最佳計算順序

本文的閱讀等級:初級

給定一序列的可乘矩陣,這些矩陣的乘積稱為矩陣鏈乘積。我們知道矩陣乘法有結合律,所以不論採用何種相乘順序,最後的結果總是一樣的。例如,A3\times 5B5\times 2C2\times 4D4\times 6 階矩陣,總計有 5 種方式刮號乘積,如下:

((AB)C)D(A(BC))D(AB)(CD)A((BC)D)A(B(CD))

雖然矩陣鏈乘積相同,但不同的乘法順序所耗費的運算量並不相同。例如,若以乘法運算為計數單位,A(BC) 需要 (5\times 2\times 4)+(3\times 5\times 4)=40+60=100 個運算,而 (AB)C 只使用 (3\times 5\times 2)+(3\times 2\times 4)=30+24=54 個運算,第二種計算方式明顯優於第一種方式。考慮一般情況,如果有 n 個矩陣相乘,如何決定最佳的矩陣乘法執行順序?這個問題不存在一般公式解。最直接的方法是比較每一種順序的運算量,不過,這僅適用於小 n 的情況。當 n=10,刮號乘積有 16,796 種可能,而當 n=20 時,總共有 6,564,120,420\approx 6\times 10^9 種可能!對於長矩陣鏈,不難理解蠻力檢查是絕對不可行的。

 
計算 n 個矩陣乘積的括號方式究竟有多少種可能?這是一個組合數學問題,答案是卡塔蘭數(Catalan number),一般項公式為

\displaystyle  C_n=\frac{1}{n+1}\binom{2n}{n},~~ n\ge 1

對於 n\ge 1,前幾項是

1,2,5,14,42,132,429,1430,4862,16796,58786,\ldots

對卡塔蘭數證明有興趣的讀者,請參閱維基百科。卡塔蘭數可以用來計算很多組合結構的個數,以下舉幾個典型的例子。

 
C_n 表示長度為 2n 的 Dyck 字個數。Dyck 字是一個有 n 個 A 和 n 個 B 組成的字串,且所有的前綴 (prefix) 字串皆滿足 A 的個數大於等於 B 的個數,下面是 n=3 的 Dyck 字:

\mathrm{AAABBB~~ABAABB~~ABABAB~~AABBAB~~AABABB}

 
C_n 表示包含 n+1 個終端頂點,也稱為樹葉,的二元樹(binary tree)的個數,下圖顯示所有 n=3 的二元數:

二元樹種類 (n=3)

C_n 表示通過連結頂點而將 n+2 邊的凸多邊形切割為三角形的方法個數,下圖為所有 n=4 的切割方式:

凸多邊形切割三角形種類 (n=4)

 
既然逐一比較矩陣鏈乘積不切實際,那麼有什麼算法能讓我們減少搜尋次數呢?也許我們應該先問:逐一比較是否包含了多餘的計算?為了讓所執行的計算步驟清楚顯示,我們設計一個簡單的遞迴演算法。針對四個矩陣乘積 ABCD,我們將它分割成兩個子序列,可能的分割方式有 (A)(BCD)(AB)(CD)(ABC)(D)。下一層次再繼續分割 BCDABCDABC,直到每個子序列僅包含一個或兩個矩陣。令 \mathrm{cost}(XYZ) 代表矩陣鏈 XYZ 的運算成本。每個序列的成本等於兩個子序列的成本之和,並再加上兩個子序列結果相乘的成本,例如,

\mathrm{cost}((AB)(CD))=\mathrm{cost}(AB)+\mathrm{cost}(CD)+(3\times 2\times 6)

下圖表示遞迴演算法的樹狀結構,此結構的樹葉總數即為卡塔蘭數。觀察發現我們確實執行了一些重複的計算,例如,ABBCCD。這正是問題所在,當矩陣鏈長度 n 增大時,越來越多不必要的計算將隨之產生。

遞迴演算法的樹狀結構

 
避免重複計算的最簡單解決方法是記住已經得到的結果。每次計算出一個特定子序列所需的最小成本後,我們便將數值儲存起來。下次如果再碰到相同的子序列,只需要讀取已經儲存的答案即可。這個想法的實現程序稱為動態規劃(dynamic programming),下面我用圖表方式解說執行細節。為了保證不進行多餘計算,我們採用由下而上的搜尋方式。首先,計算出所有相鄰的兩個矩陣的相乘成本(因為只有一種計算方式,此即為最小成本),並將結果填入下表的對應位置。列指標 X 和行指標 Y 所指定的位置代表矩陣鏈的帶頭矩陣為 X,結尾矩陣為 Y,而標記為 \ast 的位置表示不需要執行的計算。

\underline{~~~~~~~~~B~~~~~~~~C~~~~~~~~~D~~~~~~~}\\   \begin{matrix}    A&\vline&AB\\    ~&\vline&30\\    B&\vline&\ast&~&BC&~\\    ~&\vline&~&~&40\\    C&\vline&\ast&~&\ast&~&CD\\    ~&\vline&~&~&~&~&48    \end{matrix}\\  \overline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}

 
接著再計算相鄰的三個矩陣所需要的最小成本。每一特定序列僅存在兩種可能,我們分別算出它們的成本並保留最小者。例如,子序列 ABC 的最佳順序可能是 A(BC)(AB)C,各自成本計算如下:

\mathrm{cost}(A(BC))=\mathrm{cost}(A)+\mathrm{cost}(BC)+(3\times 5\times 4)=0+40+60=100

\mathrm{cost}((AB)C)=\mathrm{cost}(AB)+\mathrm{cost}(C)+(3\times 2\times 4)=30+0+24=54

我們當然選擇第二種計算方式。同樣地,子序列 BCD 的最小成本由 B(CD)(BC)D 的最小者決定:

\mathrm{cost}(B(CD))=\mathrm{cost}(B)+\mathrm{cost}(CD)+(5\times 2\times 6)=0+48+60=108

\mathrm{cost}((BC)D)=\mathrm{cost}(BC)+\mathrm{cost}(D)+(5\times 4\times 6)=40+0+120=160

下表包含矩陣鏈長度為 3 的結果。

\underline{~~~~~~~~~B~~~~~~~~~~C~~~~~~~~~~~~~D~~~~~~~}\\  \begin{matrix}    A&\vline&AB&~&(AB)C\\    ~&\vline&30&~&54\\    B&\vline&\ast&~&BC&~&B(CD)\\    ~&\vline&~&~&40&~&108\\    C&\vline&\ast&~&\ast&~&CD\\    ~&\vline&~&~&~&~&48    \end{matrix}\\  \overline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}

 
最後一個步驟是計算序列 ABCD 的最小成本,共有三種可能的順序,A(BCD)(AB)(CD)(ABC)D,利用已知的最佳子序列可以得到各自的最小成本,詳細計算過程如下:

\mathrm{cost}(A(BCD))=\mathrm{cost}(A)+\mathrm{cost}(BCD)+(3\times 5\times 6)=0+108+90=198

\mathrm{cost}((AB)(CD))=\mathrm{cost}(AB)+\mathrm{cost}(CD)+(3\times 2\times 6)=30+48+36=114

\mathrm{cost}((ABC)D)=\mathrm{cost}(ABC)+\mathrm{cost}(D)+(3\times 4\times 6)=54+0+72=126

第二個計算方式使用最少的運算量,我們將它存入對應的表格位置,完整的結果如所示:

\underline{~~~~~~~~~B~~~~~~~~~~C~~~~~~~~~~~~~~~~D~~~~~~~}\\  \begin{matrix}    A&\vline&AB&~& (AB)C&~&(AB)(CD)\\    ~&\vline&30&~& 54&~&114\\    B&\vline&\ast&~&BC&~&B(CD)\\    ~&\vline&~&~&40&~&108\\    C&\vline&\ast&~&\ast&~&CD\\    ~&\vline&~&~&~&~&48    \end{matrix}\\  \overline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}

計算矩陣鏈 ABCD 的最佳順序是 (AB)(CD),共使用 114 個乘法運算。

 
讀者如果比較 ABCD 五種執行順序的計算成本,可能會認為費了大半天功夫似乎也沒有省下多少運算量,原因其實是本文選擇了大小相近的矩陣。如果 A10\times 40B40\times 5C5\times 50,則

\mathrm{cost}((AB)C)=(10\times 40\times 5)+(10\times 5\times 50)=2000+2500=4500

\mathrm{cost}(A(BC))=(40\times 5\times 50)+(10\times 40\times 50)=10000+20000=30000

後者的計算量為前者的7倍。如果矩陣鏈持續增長,選擇最小運算成本的執行順序可以帶來更顯著的減量效果。

Advertisements
This entry was posted in 線性方程, 線性代數專欄 and tagged , , , . Bookmark the permalink.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s