動機
矩陣乘法滿足結合律,因此相容的矩陣可以用不同的括號化方式相乘,而數學上的乘積不變。然而純量乘法的次數可能相差懸殊。動態規劃透過記錄每個連續區間的最優成本,避免枚舉所有括號化方式。狀態必須同時保留兩個端點:鏈中間的一個矩陣可以參與許多維數和成本各不相同的子問題。
本單元的目標函數統計標準三重迴圈矩陣乘法算法中的純量乘法次數,不統計加法、記憶體存取、數值捨入誤差或經過優化的硬件運算。在這一成本模型下最優的次序,在實際實作中未必最快。
定義
定義 2.2.1
(矩陣鏈與區間成本)
設 為矩陣,,其中 的維數為 ,且每個 都是正整數。無論如何括號化,每個連續乘積 的維數都是 。在標準算法中,將 矩陣與 矩陣相乘需要 次純量乘法。
對 ,令 為對 完全括號化的最小成本。單個矩陣無需乘法,故 。對 ,最後一次運算必定在某個 ()之後將區間分開,其兩個輸入分別是左、右兩個連續子鏈的乘積。
定理
定理 2.2.2
(最優子結構與遞推式)
對 ,
為每個區間記錄任一取得最小值的分割點,即可重構出一個最優括號化方式。
定理 2.2.3
(動態規劃的成本)
按區間長度遞增的次序填表,共計算 個候選分割,使用 次算術運算和 個表項,並得到最優值。為每個區間再儲存一個取得最小值的分割點,需要另外 個表項。
證明思路或證明
證明
(最後分割與最優子結構)
固定一個區間和最後一次分割 。由結合律,兩個運算元恰為左、右子鏈的乘積。它們的維數分別為 和 ,因此最後一次乘法的成本如上式所示,與兩個子鏈各自如何括號化無關。若某個聲稱最優的完全括號化使用了非最優的左子鏈,則把它換成成本更低的括號化,維數和最後一次乘法的成本都不變,這與最優性矛盾。對右子鏈的論證相同。
因此,以 為最後分割的每個括號化,其成本至少等於遞推式中對應的候選值。反之,為兩個嚴格更短的子鏈各取最優括號化,再將所得結果相乘,恰好達到該候選值。對所有可能的最後分割取最小值,即證等式成立。該論證對區間長度用歸納法,從單個矩陣開始,是良基的。
重構時,為每個區間儲存一個取得最小值的 。遞歸地重構左、右區間,並在它們的乘積外加上括號。每次遞歸調用都使區間長度減小,因此必然終止。遞推式的證明說明重構所得的成本等於表中的值;若有並列最優,可任意取捨,不同取捨可能得到不同的最優括號化。
證明透視
為甚麼替換是可行的
子鏈結果的維數取決於它的端點,而不取決於其內部的括號。因此換成成本更低的括號化,不會改變最後一次乘法的成本。正是這一不變性使最優子結構的論證成立。該假設只用在一處:最後一次乘法的成本 不可取決於兩個子鏈是如何建成的。論證按區間長度歸納而告完結,因為兩個子鏈都嚴格更短,而單個矩陣是成本為零的基礎情形;並列最優並無影響,因為只斷言最小值。若合併成本確實取決於內部構造,較便宜的子鏈便可能被一個較貴、卻令最後一步更便宜的子鏈取代,遞推式就不再是等式。
證明
(候選分割與表項的計數)
長度為 的區間有 個可能的分割,這樣的區間共有 個。它們對 求和等於 :每個候選唯一對應三個下標 ,等價地,對應從 中選出的三個互不相同的切分位置。表中相關的表項共 個。按長度遞增填表,可保證兩個子問題在使用前已經算出。若維數以二進制編碼,表項可能超出一個機器字;算術運算次數並不自動等於位元複雜度上界。
例題詳解
例題 2.2.4
(括號化方式的巨大差異)
設三個矩陣的維數依次為 、 和 。先乘前兩個再乘第三個,成本為 。先乘後兩個,成本為 。兩種方式的結果維數都是 ,但前一種次序所用的純量乘法次數僅為後者的十分之一。
例題 2.2.5
(四個矩陣的表)
取維數 。長度為二的區間成本為 、、。長度為三時,,。最後, 的三個候選值為 、 和 。最優值為 ,對應分割 :。
例題 2.2.6
(並列的情形)
若三個矩陣都是 ,兩種括號化的成本均為 。兩個最後分割都是最小值點。儲存第一個取得最小值的下標,就得到一個正確的答案;算法並不要求列出所有最優解。
常見錯誤
反例模式
選擇當前成本最小的乘積
取維數 。唯一一個成本最小的初始相鄰乘積是 ,成本為 。做完這次乘法後,餘下維數為 ;下一步成本最小的乘積需要 ,最後一次乘法需要 ,總計 。反之,先乘 的成本為 ,餘下維數為 。接著乘剩下的前兩個矩陣,成本為 ,最後一次乘法的成本為 。總計 。因此,選擇當前成本最小的乘積並不總是最優的;遞推式考察的是每一種可能的最後分割。
常見錯誤
(混淆分割處的維數)
對區間 在 之後分割的候選,最後一次乘法的兩個運算元維數是 和 ,所以成本是 ,而不是 。對 ,維數為 和 ,唯一的分割是 ,成本為 ;若誤用 ,便得到 ,這並非維數相配的乘法。子鏈乘積的外側維數由其端點決定。此外,表項是成本,而不是矩陣:要得到矩陣乘積,必須先重構出運算次序,再實際執行矩陣乘法。
填表時不遺漏依賴關係
先將所有對角線表項初始化為零。然後依次處理長度 。對每個起點下標 ( 從 到 ),令 ,並計算每個分割 。兩個子區間的長度都小於 ,所以它們的表項已經可用。令 為最小的候選值,並儲存取得該值的一個下標。答案為 。當 時,關於長度的迴圈不會執行,答案就是已經初始化的零。
同一長度內各表項的計算次序無關緊要,因為它們只依賴更短的區間。相反,若不檢查依賴關係而按行由左至右填表,可能讀到尚未算出的表項。依賴圖能把這一點看得很清楚:從每個狀態向某個候選所需的狀態連邊。所有這些邊都指向更短的區間,所以區間長度就是一個拓撲序。儘管遞推式引用的是同一張表,它並不是循環定義。
例題 2.2.7
(由儲存的分割點重構)
在四個矩陣的例子中,區間 儲存的分割點為 。遞歸得到區間 和 ;它們都只有一個可能的分割。因此重構輸出 。為獨立驗證,前兩次中間乘法的成本為 和 ,結果的維數分別為 和 。最後一次乘法的成本為 ,總和為 ,與表中的值一致。
僅憑成本表,有時也可以透過重新計算各個候選值,找到與所存最小值相符者,從而還原分割點。儲存分割點可以免去這一額外搜尋,並使並列情形的處理方式明確。當多個分割下標取得相同成本時,任取其一就足以重構出一個最優解。列出所有最優括號化則是另一個輸出問題:即使成本表的大小是二次的,最優括號化的個數也可能非常大。
為甚麼局部選擇並不充分
成本最小的相鄰乘法看上去很有吸引力,因為它的成本立即可知。但這次乘積產生了新的維數,會改變後續乘法的成本。在上面的反例中,成本最小的第一步留下了一對較不利的維數。若要用交換論證,就必須證明:把某個全局最優解的第一步換成成本最小的相鄰對,絕不會增加此後的總成本。這個明確的反例證明,對這一規則而言,這樣的一般性論證不可能存在。
動態規劃避免了對第一步的猜測,而是按最後一次乘法對完全括號化方式進行分類。一旦分割確定,兩個子乘積的維數就已知,最後一步的成本因而與它們內部的次序無關。遞推式在比較候選值之前,已經計入了兩個子問題和最後一次乘法的成本。這正是它的局部比較是安全的、而只比較眼前的乘法成本卻不安全的確切原因。
完全括號化乘積的可能數目隨 迅速增長,而區間的數目只是二次的。許多候選的完全括號化使用同一個區間,所以製表時直接重用該區間的最優解,而不是重複求解。立方量級的運算次數包含了所有區間的所有分割選擇,並不需要枚舉所有完全括號化。若使用相同的狀態與遞推式做記憶化遞歸,只要每個狀態至多計算一次,狀態數和分割數的漸近量級相同。
輸入與模型的限制
維數必須按原次序匹配: 的列數必須等於 的行數。否則整個乘積沒有定義,此遞推式也不能修復這樣的輸入。
常見錯誤
(為節省乘法而調換矩陣次序)
結合律只允許括號移動,不允許調換矩陣。設 為 矩陣、 為 矩陣:乘積 有定義,大小為 ,但 沒有定義,因為 有 列而 只有 行。因此按大小為矩陣鏈排序,會改變問題或使它失去意義;遞推式只是為給定的次序選擇括號。
上述計數使用的是 與 矩陣相乘的標準成本 。其他乘法算法,或對加法另行計費的模型,會改變遞推式中的局部成本。只有當替換性質仍然成立時,同樣的動態規劃結構才依然有效:相關的結果大小以及合併子結果的成本,必須取決於狀態中所包含的資訊。在數值浮點運算中,改變括號還可能改變捨入後的結果,儘管精確的矩陣乘法滿足結合律。本筆記優化的是在所聲明的純量乘法模型下的精確代數乘積。
立方量級的運算次數上界假設表項上的算術運算成本為單位成本。若輸入維數很大,則每個成本是可能遠大於任一維數的整數,精確比較與加法的位元運算成本便取決於其長度。使用任意精度整數時,遞推式仍然正確;機器模型只影響執行時間的核算。每當某個數值參數是以二進制給出、而不是真有那麼多個物件的列表時,這一區分都很有用。
理解候選數目
有一種直接的方式可以看出這個二項式係數。用三個切分位置 表示一個候選,這三個位置取自 且滿足 。反之,任意三個遞增的切分位置恰好確定一個區間和一個合法分割。因此候選數目就是 個位置中三元子集的個數。對 ,得到十個,與逐一統計的長度為二的三個、長度為三的四個、長度為四的三個候選一致。這一計數針對的是比較的候選,而不是實際求矩陣乘積時所用的純量乘法。
概念視角組合
括號化即多邊形的三角剖分
當 ,把切分位置 當作凸 邊形的頂點。矩陣 對應連接頂點 與 的邊,另有一條封閉邊連接 與 。 的每個完全括號化,就是這個多邊形的一個三角剖分:區間 在 之後的最後分割,是頂點為 的三角形,其成本恰為 ;兩個子鏈則是被邊 和 截出的兩個子多邊形。因此括號化的總成本等於各三角形的 之和,遞推式就是最小權三角剖分的標準遞推式,而上面數出的 的三元子集,正是所有可能的三角形。
實作取最小值時,由於區間長度大於一,每個區間至少有一個候選。將其最佳值初始化為第一個候選,再與其餘候選比較;對角線單獨處理。這樣可避免把未初始化的表值與真正為零的成本混淆。正的維數保證任何非平凡乘法在此模型中的成本為正,不過一旦給定合法的局部成本,算法的歸納證明並不需要這一正性。
這一證明還說明,同樣的一般技巧只有在仔細選定狀態之後才適用於其他區間問題。若合併兩個子解的成本取決於某個會隨其內部構造而變化的隱藏性質,那麼只儲存最小成本,可能丟掉一個較貴、卻使後續合併便宜得多的子解。此處不存在這樣的隱藏維度: 的每一種括號化都得到相同的矩陣維數。這一事實應當在寫出遞推式之前就加以確立,而不是當作遞推式本身的推論來假定。
總結
每個括號化都有一個最後分割。兩個所得的子鏈可以獨立優化,因為它們的結果維數由端點所決定。按區間長度遞增計算遞推式,只需立方量級的算術運算,而記錄下來的分割點可重構出一個最優次序。
練習
快速檢查
(對維數 計算兩種括號化的成本,並選出一個最優解。)
分別計算兩種括號化的成本。
解答 · 答案
先乘左邊的成本為 ;先乘右邊的成本為 。先乘左邊是最優的。
快速檢查
( 是多少?為甚麼?)
回想遞推式對只含一個矩陣的區間怎樣規定。
解答 · 答案
它等於零,因為單個矩陣本身就是它自己的乘積,不需要任何純量乘法。
快速檢查
(當 時,該表共計算多少個候選分割?)
分別數出每種區間長度的候選數目,再相加。
解答 · 答案
個數為 :長度為二的區間有三個候選,長度為三的有四個,長度為四的有三個。
快速檢查
(若每個矩陣都是 ,則 個矩陣的任一完全括號化的成本是多少?)
先數二元矩陣乘法的次數。
解答 · 答案
每個完全括號化恰好使用 次二元矩陣乘法,每次成本為 ,所以總成本為 。