動态規劃之矩陣鍊乘法（第15章）

實驗室催促畢業論文進展，是以今天下午我得收拾一下，準備一下畢業論文需要弄的東西。 唉， 感覺自己就是太笨了。 ——題外話。

1.動态規劃的原理

[1] 什麼情況下使用動态規劃？

　　适合應用動态規方法的求解最優化問題應該具備兩個要素：最優子結構和子問題重疊。使用動态規劃方法求解最優化問題的第一步就是刻畫最優解的結構。如果一個問題的最優解包含子問題的最優解，我們就成此類問題具有-最優解結構-性質。第二個條件子問題重疊，子問題的空間足夠的小，即問題的遞歸算法會反複的求解相同的子問題，而不是一味的生成新的子問題。如果遞歸算法反複求解相同的子問題，我們就稱最優化問題具有-重疊子問題-的性質。動态規劃算法通常利用重疊子問題的性質：對每個子問題求解一次，将解存入一個表中，當再次需要這個子問題的時候直接查表，每次查表的代價為常量時間。

　　

[2] 重構最優解和備忘機制　

　　從實際的角度考慮我們通常将每個子問題所做的選擇存在一個表中，這樣就不需要根據代價值來重構這些資訊。

　　備忘機制：在遞歸的算法中加入備忘機制，可以讓自頂向下的遞歸算法達到和自底向上的動态規劃算法相似的效率。

　　

2.矩陣鍊乘法概述

Description

給定n個矩陣｛A1,A2,…,An｝，其中Ai與Ai+1是可乘的，i=1,2 ,…,n-1。如何确定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數乘次數最少。

Input

有N個矩陣連乘,用一行有n+1個數數組表示,表示是n個矩陣的行及第n個矩陣的列,它們之間用空格隔開.

Output

你的輸出應該有C行，即每組測試資料的輸出占一行，它是計算出的矩陣最少連乘積次數，輸出最優全括号結構

3.矩陣鍊乘法算法分析與設計

矩陣鍊乘法問題動态規劃分析：

給定由n個矩陣構成的序列[A1，A2，…，An]，對乘積A1A2…An，找到最小化乘法次數的加括号方法。

1）尋找最優子結構

　　此問題最難的地方在于找到最優子結構。對乘積A1A2…An的任意加括号方法都會将序列在某個地方分成兩部分，也就是最後一次乘法計算的地方，我們将這個位置記為k，也就是說首先計算A1…Ak和Ak+1…An，然後再将這兩部分的結果相乘。

最優子結構如下：假設A1A2…An的一個最優加括号把乘積在Ak和Ak+1間分開，則字首子鍊A1…Ak的加括号方式必定為A1…Ak的一個最優加括号，字尾子鍊同理。一開始并不知道k的确切位置，需要周遊所有位置以保證找到合适的k來分割乘積。

2）構造遞歸解

　　設m[i,j]為矩陣鍊Ai…Aj的最優解的代價，則

┌ 0 如果i = j

m[i,j] = │

└ min(i≤k＜j) {m[i,k] + m[k+1,j] + Ai.row*Ak.col*Aj.col} 如果i ＜ j

3）建構輔助表，解決重疊子問題

　　從第二步的遞歸式可以發現解的過程中會有很多重疊子問題，可以用一個n*n維的輔助表 m[n, n]來儲存子問題的解，表中每個元素包含2個資訊，分别是最優乘積代價及其分割位置k 。輔助表 m[n, n]可以由2種方法構造，一種是自底向上填表建構，該方法要求按照遞增的方式逐漸填寫子問題的解，也就是先計算長度為2的所有矩陣鍊的解，然後計算長度3的矩陣鍊，直到長度n；另一種是自頂向下填表的備忘錄法，該方法将表的每個元素初始化為某特殊值(本問題中可以将最優乘積代價設定為一極大值)，以表示待計算，在遞歸的過程中逐個填入遇到的子問題的解。

　　備忘錄法會比自底向上法慢一個常數因子，因為前者有遞歸調用的代價，維護表格的開銷也稍大。不過如果動态規劃中有些的子問題是不需要的話，自頂向下可能會少計算一些子問題。

4）建構最優解

　　雖然m[n, n]可以記錄矩陣鍊乘積所需的最小的标量乘法的運算次數，但是它并沒有直接支出如何進行這種最優代價的矩陣鍊乘法的計算完全加括号的方式。輔助表s[1…n-1,2….n]記錄了構造最優解所需的資訊。每個表項s[i,j]記錄一個k值，指出 AiAi+1......Aj 最優括号化方案的分割點應該在 Ak和Ak+1 之間。

核心算法設計：

4.矩陣鍊乘法Java實作

矩陣鍊乘法核心類

//矩陣鍊乘法核心類
package lbz.ch15.dp.ins2;

/**
 * @author LbZhang
 * @version 建立時間：2016年3月9日 上午10:29:42
 * @description 矩陣鍊乘法核心類
 */
public class MatrixChain {
    public static Pair matrixChainOrder(int[] p) {
        int n = p.length - ;
        int i, j, L, k, q;
        int[][] m = new int[n + ][n + ];
        int[][] s = new int[n + ][n + ];
        for (i = ; i <= n; i++) {
            m[i][i] = ;
        }
        for (L = ; L <= n; L++) { // /L是子矩陣鍊的長度
            for (i = ; i <= n - L + ; i++) { // /這個地方n也算是一個 eg 6-2+1=5 5,6
                                                // 就是一組
                j = i + L - ; // /這個地方我們可以分析得 j-L+1=i 類似于上面一行的說明解釋
                m[i][j] = Integer.MAX_VALUE; // /預先設定m[i][j]等于無窮大
                for (k = i; k <= j - ; k++) {
                    q = m[i][k] + m[k + ][j] + p[i - ] * p[k] * p[j]; // /用于暫時存儲i-j子矩陣鍊中的求解的值
                    // 由于全部加括号 那麼互相之間構成括号結合的兩項肯定是互相靠近在一起的兩項
                    if (q < m[i][j]) {
                        m[i][j] = q;
                        s[i][j] = k; // /分裂位置就是k加括号的位置
                    }
                }
            }
        }
        return Pair.make(m, s);
    }

    public static void printOptimalParens(int[][] s, int i, int j) {
        if (i == j) {
            System.out.printf("A%d", i);
        } else {
            System.out.print("(");
            printOptimalParens(s, i, s[i][j]);
            printOptimalParens(s, s[i][j] + , j);
            System.out.print(")");
        }
    }
}
           

矩陣鍊乘法輔助類

package lbz.ch15.dp.ins2;
/** 
 * @author LbZhang
 * @version 建立時間：2016年3月9日 上午10:36:20 
 * @description 矩陣鍊乘法輔助類
 */
public class Pair {
    public static int[][] mm ;
    public static int[][] ss;


    public static Pair make(int[][] m, int[][] s) {
        mm = m;
        ss = s;
        return null;
    }
    /**
     * 調用方法
     * @param args
     */
    public static void main(String[] args) {
        int[] p = {,,,,,,};
        MatrixChain.matrixChainOrder(p);
        MatrixChain.printOptimalParens(Pair.ss, , );
    }

}