前言
- 三部曲如下三步：
- 基本原則：“空間換時間” 存儲重復子問題的解，減少運算時間
- 底層運算：“表格操作” 用表格存儲子問題的解
- 實現(xiàn)路線：“子問題劃分、自底向上求解” 利用表格中存儲的子問題的解，求上一層子問題的解。
一、矩陣連乘問題
1、問題描述
2、完全加括號
矩陣連乘計算次序 可以用 加括號的方式 來確定。特別的，完全加括號的矩陣連乘積可遞歸地定義為：
- 單個矩陣是完全加括號的
- 矩陣連乘積 A 是完全加括號的，則 A 可示為2個完全加括號的矩陣連乘積 B 和 C 的乘積并加括號，即 A=（BC）
3、問題分析
給定n個矩陣??1,?, ????，其中第i個矩陣的維度為??(???1)×????，以及它們的一個完全加括號方案：
4、最優(yōu)子結(jié)構性質(zhì)
構建原問題最優(yōu)解 與 子問題最優(yōu)解之間的關系：
5、狀態(tài)表示和遞推方程
6、自問題個數(shù)和求解順序
二、計算最優(yōu)值示例
1、問題描述
2、計算最優(yōu)值示例*****
按以下順序計算：
-
第一次計算（遍歷）：
m(1,2)=30 * 35 * 15 = 15750m(2,3)=35 * 15 * 5 = 2625m(3,4)=15 * 5 * 10 = 750m(4,5)=5 * 10 * 20 = 1000m(5,6)=10 * 20 * 25 = 5000 -
第二次計算（遍歷）
-
m(1,3)=7875時，有兩種情況，k = 1 或者 k =2 時，(下面的數(shù)據(jù)就可以使用上面算法的，這就是自底向上)
k=1時，m(1,1)+m(2,3)+30 * 35 * 5= 7875
k=2時，m(1,2)+m(3,3)+30 * 15 * 5= 23000
最小的值為7875， -
m(2,4)=4375時，有兩種情況，k = 2 或者k =3 時，（同上）
k = 2時，m(2,2)+m(3,4)+35 * 15 * 10 = 6000
k = 3時，m(2,3)+m(3,3)+35 * 5 * 10 = 4375
最小的值為 4375 - 后面同上計算，依次是：
-
m(3,5)=2500，k=3 或者 k=4 -
m(4,6)=3500，k=4 或者 k=5
-
-
第三次計算（遍歷）
-
m(1,4)=9375時，k 有三次情況，k=1，k=2，k=3，（同上）
k=1時，m(1,1)+m(2,4)+30 * 35 * 10 = 14875
k=2時，m(1,2)+m(3,4)+30 * 15 * 10 = 21000
k=3時，m(1,3)+m(4,4)+30 * 5 * 10 = 9375 -
m(2,5)=7125時，k 有三次情況，k=2，k=3，k=4
k = 2，m(2,2)+m(3,5)+35 * 15 * 20 = 13000
k = 3，m(2,3)+m(4,5)+35 * 5 * 20 = 7125
k = 4，m(2,4)+m(5,5)+35 * 10 * 20 = 11375 -
m(3,6)=5375
-
-
第四次計算（遍歷）
-
m(1,5)=11875時，k 有四次情況，k=1，k=2，k=3，k=4，（同上）
k=1時，m(1,1)+m(2,5)+30 * 35 * 20 = 28125
k=2時，m(1,2)+m(3,5)+30 * 15 * 20 = 27250
k=3時，m(1,3)+m(4,5)+30 * 5 * 20 = 11875
k=4時，m(1,4)+m(5,5)+30 * 10 * 20 = 15375 -
m(2,6)=10500
-
-
第五次計算（遍歷）
-
m(1,6)= 15125時，k 有五次情況，k=12345，（同上）
k = 1時，m(1,1)+m(2,6)+30 * 35 * 25 = 36750
k = 2時，m(1,2)+m(3,6)+30 * 15 * 25 = 34250
k = 3時，m(1,3)+m(4,6)+30 * 5 * 25 = 15125
k = 4時，m(1,4)+m(5,6)+30 * 10 * 25 = 21875
k = 5時，m(1,5)+m(5,5)+30 * 20 * 25 = 26875
-
3、構造最優(yōu)解
4、算法實現(xiàn)
import java.util.Scanner;
/**
* DP 算法之 矩陣連乘
*/
public class Main {
public static long[][] memoTable; // 存放局部最優(yōu)值
public static int[][] bestK ; // 存放 劃括號k 的位置
public static int[] dim ; // 存放矩陣的值
public static int matrixNum; // 二位矩陣 的維度
/**
* 自底向上地計算最優(yōu)值，結(jié)果保存在全局變量memoTable和bestK中
* @param matrixNum
* @return
*/
static long MatrixChain(int matrixNum) {
int i,j,len,k;
for(i=1; i<=matrixNum; i++) //單個矩陣的情形，定義數(shù)乘次數(shù)為0
memoTable[i][i] = 0;
for(len=2; len<=matrixNum; len++){ //計算長度為len的矩陣鏈最優(yōu)值
for(i=1; i<=matrixNum-len+1; i++) { //矩陣鏈的開始矩陣下標
j = i+len-1; //矩陣鏈的結(jié)束矩陣下標
memoTable[i][j] = 100000000; //預定義的一個充分大數(shù)
for(k=i; k<j; k++) { //枚舉劃分位置
long ans = memoTable[i][k] + memoTable[k+1][j] +
dim[i-1]*dim[k]*dim[j];
if (ans < memoTable[i][j]){ //更新最優(yōu)信息
bestK[i][j] = k;
memoTable[i][j] = ans;
}
}//end of for k
}//end of for i
}//end of for len
return memoTable[1][matrixNum];
}
/**
* 遞歸構造最優(yōu)解
* @param i
* @param j
* @param bestK
* @return
*/
public static String traceback(int i,int j,int[][] bestK) {
if(i==j) {
return String.format("A%s", i);
}
if(i==j-1){
return String.format("A%sA%s", i, j);
}
int position = bestK[i][j];
StringBuilder sb = new StringBuilder();
if(i!=position) {
sb.append("(");
}
sb.append(traceback(i, position, bestK));
if(i!=position) {
sb.append(")");
}
if(position+1!=j) {
sb.append("(");
}
sb.append(traceback(position+1, j, bestK));
if(position+1!=j) {
sb.append(")");
}
return sb.toString();
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("請輸入矩陣的個數(shù)：");
matrixNum = in.nextInt();
System.out.println("請輸入矩陣的行數(shù)和列數(shù):");
dim = new int[matrixNum+1];
for(int i = 0;i <= matrixNum;i++) {
dim[i] = in.nextInt();
}
memoTable = new long[matrixNum+1][matrixNum+1];
bestK = new int[matrixNum+1][matrixNum+1];
long min = MatrixChain(matrixNum);
System.out.println("矩陣連乘的最小次數(shù)是：" + min);
System.out.println(String.format("矩陣的連乘次序：%s", traceback(1, matrixNum, bestK)));
}
}
三、基本要素-最優(yōu)子結(jié)構
- 最優(yōu)子結(jié)構性質(zhì)，通俗地講就是問題的最優(yōu)解包含其子問題的最優(yōu)解。也就是說，如果把問題的最優(yōu)解分解（比如劃分為兩個或者多個部分，或者刪除第一個或者最后一個分量），得到一個子解，那么這個
子解是其相應子問題的最優(yōu)解。
- 最優(yōu)子結(jié)構性質(zhì)隱含了問題最優(yōu)解和子問題最優(yōu)解之間的一種遞推關系。它是動態(tài)規(guī)劃的基礎，遞推方程是最優(yōu)子結(jié)構性質(zhì)的體現(xiàn)。
- 在分析問題的最優(yōu)子結(jié)構性質(zhì)時，人們一般采用
反證法：首先假設由問題最優(yōu)解S導出的子問題的解不是最優(yōu)的，然后再推導在這個假設下可構造出比S更好的解 S’，從而得到矛盾。
四、基本要素-重疊子問題
- 遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質(zhì)稱為
子問題的重疊性質(zhì)。 - 動態(tài)規(guī)劃算法，
對每一個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果。 - 通常不同的子問題個數(shù)隨問題的大小呈
多項式增長。因此用動態(tài)規(guī)劃算法只需要多項式時間，從而獲得較高的解題效率。 【降低復雜度不是本章的目標了?。?/code>】
五、遞歸方法
long MatrixChain(int i, int j){
if (i == j) {//單個矩陣的情形
memoTable[i][j] = 0;
return 0;
}
long ans, min = 100000000;//預定義的一個充分大數(shù)
for (int k=i; k<j; k++) {
ans = MatrixChain(i,k) + MatrixChain(k+1,j)
+ dim[i-1]*dim[k]*dim[j]; //遞歸計算
if (ans < min) {
min = ans;
}
}
return min; }
文章來源：http://www.zghlxwxcb.cn/news/detail-484017.html
六、備忘錄方法
文章來源地址http://www.zghlxwxcb.cn/news/detail-484017.html
//遞歸調(diào)用前用 memset(memoTable,-1,sizeof(memoTable))初始化備忘錄表為-1
long MatrixChainMemo(int i,int j){
if (memoTable[i][j] != -1)
return memoTable[i][j]; //備忘錄表中有答案，則跳出遞歸調(diào)用過程
if (i == j) {//單個矩陣的情形
memoTable[i][j] = 0;
return 0;
}
long ans,max = 100000000;//預定義的一個充分大數(shù)
for (int k=i; k<j; k++) {
ans = MatrixChainMemo(i,k)+MatrixChainMemo(k+1,j)
+dim[i-1]*dim[k]*dim[j]; //遞歸計算
if (ans < max) {
bestK[i][j]=k;
max = ans;
}
}
memoTable[i][j] = max; //用遞歸執(zhí)行結(jié)果更新備忘錄表
return max;
}
七、動態(tài)規(guī)劃算法設計的步驟
- 分析最優(yōu)解的性質(zhì)，并刻劃其
最優(yōu)子結(jié)構特征； - 確定
狀態(tài)表示S(x~1~,x~2~,…)和狀態(tài)遞推方程，遞歸地定義最優(yōu)值； - 確定
狀態(tài)轉(zhuǎn)移順序，以自底向上的方式計算出最優(yōu)值；（從最小問題計算起，保存最優(yōu)子結(jié)果，在計算更大的問題時就可以調(diào)用之） - 根據(jù)計算最優(yōu)值時得到的信息，
構造最優(yōu)解。
到了這里，關于動態(tài)規(guī)劃算法學習一：DP的重要知識點、矩陣連乘算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
