-
1.1具體實體
1.2子問題的劃分和遞推方程 -
2.動態規劃演算法的遞回實作
-
3.動態規劃演算法的迭代實作
-
4.動態規劃演算法的要素
這里用矩陣鏈的乘法問題來說明動態規劃演算法的設計要素，
\(A_1,A_2,..,A_n\)表示\(n\)個矩陣的序列，其中\(A_i\)為\(P_{i-1} \times P_i\)階矩陣，\(i=1,2,...,n\)，
向量\(P=<P_0,P_1,P_2..P_i>\)表示矩陣鏈的輸入，其中\(P_0\)是\(A_1\)的行數，\(P_1\)是\(A_1\)的列數，\(P_1\)是\(A_2\)的行數，以此類推，
計算這個矩陣需要做\(n-1\)次兩個矩陣的相乘運算，可以用\(n-1\)對括號表示運算次序，
因為矩陣乘法滿足結合律，所以無論采用那種順序，最后結果都一樣，但是采用不同的順序計算的作業量不同，如何定義兩個矩陣相乘的作業量呢？
所以假設\(A_1\)有\(i\)行\(k\)列，\(A_2\)有\(k\)行\(j\)列，所以\(A_1\)\(A_2\)相乘后的矩陣有\(i\)行\(j\)列，含\(ij\)個元素，
以元素相乘作為基本運算，乘積中每個元素的計算都需要做j次乘法，于是計算\(A_1A_2\)總共需要\(ijk\)次乘法，
1.1具體實體
假設輸入的是\(P=<10,100,5,50>\),說明有\(3\)個矩陣相乘，其中，
\(A_1:10 \times 100\)
\(A_2:100\times 50\)
\(A_3:5 \times50\)
有兩種乘法次序：
\((A_1A_2)A_3\)
\(A_1(A_2A_3)\)
執行第一種運算的基本運算次序：\(10 \times 100\times5 + 10 \times 5 \times 50=7500\)
執行第二種運算的基本運算次序：\(10 \times 100\times50 + 100 \times 5 \times 50=75000\)
作業量相差達10倍！
所以我們的問題是：給定向量P，確定一種乘法次序，使得基本運算的總次數最少，
蠻力演算法時間復雜度太大，這里先不討論，
我們嘗試用動態規劃演算法，從子問題的劃分，遞回方程的確定，遞回和迭代的實作方法，復雜度分析等方面介紹動態規劃演算法，
1.2子問題的劃分和遞推方程
我們的優化目標是：基本運算次數的最小化，
如何界定子問題的邊界？ 令\(A_i..n\)表示輸入的矩陣鏈，
如果從前向后劃分，得\(A_{1..i}\)，i=1,2,...,n，得到的子問題只有后邊界，但是在計算子問題\(A_{1..j}\)，j>i時，我們不僅需要知道子問題\(A_{1..i}\)，也得知道\(A_{i+1..j}\)的資訊，
這說明子問題的劃分需要前后兩個邊界，
用\(A_i..j\)定義矩陣鏈\(A_i,A_{i+1},..,A_j\)相乘的子問題，\(m[i,j]\)表示得到乘積\(A_{i..j}\)所用到的最小基本運算次數，
假定最后一次乘積發生在矩陣鏈\(A_{i..k}\)和\(A_k+1..j\)之間，即
\(A_iA_{i+1}..A_j=(A_iA_{i+1}..A_k)(A_{k+1}A_{k+2}..A_j)\)
\(k=i,i+1,...,j-1\)
所以子問題\(A_i..j\)的計算依賴于子問題\(A_i..A_k\)和\(A_{k+1}..A_j\)的計算結果，
即\(m[i,j]\)依賴于\(m[i,k]\)和\(m[k+1,j]\)的值，
k代表子問題的劃分問題，考慮所有可能的劃分，\(i<=k<=j\)，從中比較出最小的值，
\(P_{i-1}P_kP_j\)是最后把兩個子矩陣鏈\(A_{i..k}\)和\(A_{k+1}..j\)的結果矩陣相乘所做的基本運算次數，
當\(i=j\)時，矩陣鏈只有一個矩陣\(A_i\)，這時乘法次數是\(0\)，對應了遞推式的初值，
所以這個問題是滿足優化原則的，因為當\(m[i,j]\)達到最小值時，子問題的優化函式值\(m[i,k]\)和\(m[k+1,j]\)也是最小的，
2.動態規劃演算法的遞回實作
為了確定每次相乘時加括號的位置，需要設計表\(s[i,j]\)記錄\(m[i,j]\)達到最小值時k的劃分位置，
演算法RecurMatrixChain(P,i,j)
輸入：矩陣鏈\(A_i..j\)的輸入為向量\(P=<P_0,P_1,P_2..P_i>\)，其中\(i<=k<=j\)
輸出：計算\(A_{i..j}\)的所需最小乘法次數\(m[i,j]\)和最后一次運算的位置\(s[i,j]\)
if i=j
then m[i,j] <- 0 ; s[i,j] <- i ; return m[i,j]
m[i,j] <- 無窮
s[i,j] <- i
for k <- i to j-1 do //考慮所有可能的劃分位置
q <- RecurMatrixChain(P,i,k) + RecurMatrixChain(P,k+1,j) + Pi-1PkPj
if q < m[i,j]
then m[i,j] <- q
s[i,j] <- k
return m[i,j]
求解n個矩陣相乘，只需代入i=1，j=n，
下面考慮時間復雜度
演算法在行5執行for回圈，k從1到n-1，
每次進入回圈體都在行6進行兩個子問題的遞回求解，其余作業量都是常數時間，
化簡得：
現在介紹一個定理：當\(n>1\)時，
證明：\(n=2，T(2)>=C=C_12^{n-1}，C_1=C/2\)為某個正數
假設對于任何小于n大于等于2的k，\(T(k)>=C_12^{k-1}\)，則存在某個常數C’，使得
可以看到，通過使用了動態規劃的設計思想，相比于蠻力演算法，時間復雜度有所改善，但是并沒有得到多項式時間的高效演算法，為什么？
以矩陣鏈\(A_{1..5}\)為例：
時間復雜度高的原因：在遞回呼叫中同一個子問題被多次重復計算，
在整個遞回計算中總計產生了\(1+8+24+32+16=81\)個子問題，
規模為1的子問題有5個，以此類推，得到不同的子問題個數只有\(5+4+3+2+1=15\)個
說明演算法計算的81個子問題中有許多是重復的，
3.動態規劃演算法的迭代實作
迭代計算的關鍵
- 每個子問題只計算一遍
- 迭代程序
- 從最小子問題開始
- 考慮計算順序，以保證后面用到的值前面已經計算好
- 存盤結構保存計算結果--備忘錄（存盤子問題的優化函式值和劃分邊界）
- 解的追蹤
- 設計標記函式標記每步的決策
- 考慮根據標記函式追蹤解的演算法
\(r\)為鏈長
演算法MatrixChain(P,n)
輸入：矩陣鏈\(A_{1..n}\)的輸入向量\(P=<P_0,P_1,P_2..P_i>\)
輸出：計算\(A_{i..j}\)的所需最小乘法次數\(m[i,j]\)和最后一次運算的位置\(s[i,j]\)
令所有的m[i,j]得初值為0
for r<-2 to n do //r為鏈長（子問題規模）
for i<-1 to n-r+1 //左邊界i，n-r+1是最后一個r鏈的前邊界
j<-i+r-1 //右邊界
m[i,j] <- m[i+1,j] + Pi-1PiPj
s[i,j] <- i
for k<-i+1 to j-1 do
t<-m[i,k]+m[k+1,j]+Pi-1PiPj
if t<m[i,j]
then m[i,j]<-t
s[i,j]<-k
時間復雜度：
行2,3,7都是\(O(n)\)，嵌套回圈執行\(O(n^3)\)次，內部為\(O(1)\)，\(W(n)=O(n^3)\)
解的追蹤：
\(S[1,5]=3 => (A_1A_2A_3)(A_4A_5)\)
\(S[1,3]=1 => A_1(A_2A_3)\)
輸出：
計算順序：\((A_1(A_2A_3))(A_4A_5)\)
最少的乘法次序：\(m[1,5]=11875\)
兩種比較的實作：
遞回實作：時間復雜度高，空間少
迭代實作：時間復雜度低，空間消耗多
原因：遞回實作子問題多次重復計算，子問題計算次數呈指數增長，迭代實作每個子問題只計算一遍，
動態規劃時間復雜度：
備忘錄各項計算量之和+追蹤解的作業量
通常追蹤解的作業量不超過計算作業量，是問題規模的多項式函式
4.動態規劃演算法的要素：
- 劃分子問題，確定子問題邊界，將問題求解變成多步判斷的程序，
- 定義優化函式，以該函式極大（或極小）值作為依據，確定是否滿足優化原則，
- 列優化函式的遞推方程和邊界條件，
- 自底向上計算，設計備忘錄（表格），
- 考慮是否需要設立標記函式，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65501.html
標籤：其他
上一篇：資料結構導論之第五章圖