給定一序列的可乘矩陣，這些矩陣的乘積稱為矩陣鏈乘積。我們知道矩陣乘法有結合律，所以不論採用何種相乘順序，最後的結果總是一樣的。例如，$$A$$ 是 $$3\times 5$$，$$B$$ 是 $$5\times 2$$，$$C$$ 是 $$2\times 4$$，$$D$$ 是 $$4\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），一般項公式為
$$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 組成的字串，且所有的部分字串皆滿足 A 的個數大於等於 B 的個數，下面是 $$n=3$$ 的 Dyck 字：
$$\mathrm{AAABBB~~ABAABB~~ABABAB~~AABBAB~~AABABB}$$
■ $$C_n$$ 表示包含 $$n+1$$ 個終端節點，也稱為葉子，的二元樹（binary tree）的個數，下圖顯示所有 $$n=3$$ 的二元數：
■ $$C_n$$ 表示通過連結頂點而將 $$n+2$$ 邊的凸多邊形切割為三角形的方法個數，下圖為所有 $$n=4$$ 的切割方式：
既然逐一比較矩陣鏈乘積不切實際，那麼有什麼算法能讓我們減少搜尋次數呢？也許我們應該先問：逐一比較是否包含了多餘的計算？為了讓所執行的計算步驟清楚顯示，我們設計一個簡單的遞迴演算法。針對四個矩陣乘積 $$ABCD$$，我們將它分割成兩個子序列，可能的分割方式有 $$(A)(BCD)$$，$$(AB)(CD)$$，$$(ABC)(D)$$。下一層次再繼續分割 $$BCD$$，$$AB$$，$$CD$$ 和 $$ABC$$，直到每個子序列僅包含一個或兩個矩陣。令 $$\mathrm{cost}(XYZ)$$ 代表矩陣鏈 $$XYZ$$ 的運算成本。每個序列的成本等於兩個子序列的成本之和，並再加上兩個子序列結果相乘的成本，例如，
$$\mathrm{cost}((AB)(CD))=\mathrm{cost}(AB)+\mathrm{cost}(CD)+(3\times 2\times 6)$$
下圖表示遞迴演算法的樹狀結構，此結構的葉子總數即為卡塔蘭數。觀察發現我們確實執行了一些重複的計算，例如，$$AB$$，$$BC$$，$$CD$$。這正是問題所在，當矩陣鏈長度 $$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$$ 五種執行順序的計算成本，可能會認為費了大半天功夫似乎也沒有省下多少運算量，原因其實是本文選擇了大小相近的矩陣。如果 $$A$$ 是 $$10\times 40$$，$$B$$ 是 $$40\times 5$$，$$C$$ 是 $$5\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$$
後者的計算量為前者的 8 倍。如果矩陣鏈持續增長，選擇最小運算成本的執行順序可以帶來更顯著的減量效果。
沒有留言:
張貼留言