DP之矩陣連乘問題

最優二叉查找樹的一道思考習題

同最優二叉查找樹一樣，矩陣連乘問題也是一個卡特蘭數問題（其動态規劃的構造過程都很像）

分析解答：

a，鋪墊的數學知識首先要搞清楚矩陣相乘是怎麼乘的：

1）對于連續的n個矩陣相乘 A1 * A2 *A3.........An，其乘法順序可以是任意的，可以在上面加括号，改變做乘法的順序，例如 A*B*C三個矩陣相乘可以A*(B*C)

也可以直接按從左到右的順序。連續的兩個矩陣的位數必須滿足m*p，p*n才能相乘，且相乘後的結果是個m*n的矩陣。（線性代數的知識）

2）對于2個m*p，p*n的矩陣相乘，共做乘法次數為 m*n*p 次。這是預備知識，知道矩陣連續的乘法的運算次數跟運算順序有關後，就很容易舉出例子了，略。

b，卡特蘭數個，證明很麻煩，有時間看了組合數學再來看

c，重點是要解決這個問題。

設M[i , j]表示從第 i 個矩陣到第 j 個矩陣連乘的最少乘法次數，（i 從 0 編号），我們最終的目标是求 M[0 , n-1]。

Ai *.......Ak * Ak+1.....Aj

假設要得到這個式子的值（即從矩陣 i 連乘到矩陣 j），所作的最後一個矩陣乘法是在矩陣 k 後(注意準确的描述位置)斷開的（即左右都已乘運算好），那麼容易得到

其遞推式：

M[i , j]  =  min{ M[i , k] + M[k+1 , j]  + p[i - 1] * p[ k ] * p[ j ] }         i   <=   k   <=   j-1

其中 di 是矩陣 Ai 的第一維，dk+1是斷開處矩陣 Ak 的第二維（即Ak+1的第一維，是一樣的），dj+1是最後一個矩陣 Aj 的第二維。

得到這個式子也是一個逆向思維的過程。

可以用矩陣連乘的動态規劃構造過程與最優二叉查找樹比較下，發現其構造非常相似（在前面一篇dp之什麼叫做professional中提到過，不再詳述）

實作：

初始條件：M[i , i] = 0

填表順序：鑒于其遞推式與最優二叉查找樹相似，填表順序也是按對角線的，自己畫畫就知道了。

代碼也跟最優二叉查找樹的控制邏輯相似：

package Section8;

/*第八章 動态規劃   課後習題：矩陣連乘*/

public class MatEven {

    /**

     * @param args

     */

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        int[] Dim = {30,35,35,15,15,5,5,10,10,20,20,25};

        int result = MatEven(Dim);

        System.out.println("\n動态規劃求的的最優政策相乘順序導緻的最少乘法數為：" + result);

    }

    public static int MatEven(int[] Dim){

        //接受n個矩陣的次元數組Dim大小為2n

        int n = Dim.length / 2;        //有n個矩陣，編号0...n-1,編号為k的矩陣的維數是Dim[2k] * Dim[2k+1]

        int[][] Result = new int[n][n];        //最小代價矩陣

        //初始化

        for(int i = 0;i < n;i++)

            Result[i][i] = 0;

        //沿對角線填矩陣

        for(int d = 1;d <= n-1;d++)      //共n-1條對角線需要填

        {

            for(int i = 0;i <= n-d-1;i++)    //第d條對角線的第一個點橫坐标為d

            {

                //int j = i - d;

                int j = i + d;        //在第d條對角線上的點，橫縱坐标的關系是j = i + d

                //這樣就确定了一個位置（i,j）的坐标，然後來填（i,j）

                int Min = 1000000000;

                for(int k = i;k <= j-1;k++)        //從第k個矩陣後面斷開

                {

                    //動态規劃狀态轉移方程

                    int temp = Result[i][k] + Result[k+1][j] + (Dim[2*i] * Dim[2*k + 1] * Dim[2*j+1]);

                    if( temp < Min)

                        Min = temp; 

                }

                Result[i][j] = Min;

            }

        }

        return Result[0][n-1];

}

上面用一個數組接受一個連乘的矩陣的維數，

例如連乘的矩陣維數是：30*35　　35*15　　15*5　　5*10　　10*20　　20*25

用動态規劃求解得到的最佳乘法次數是：

動态規劃求的的最優政策相乘順序導緻的最少乘法數為：15125

直接傳回矩陣的話就可以得到整個M[i , j]的值

如果按照從左到右的順序做乘法，是遠遠不止這個次數的。

-------------------------------------------------------------------------

當然，再做一些處理，就還可以得到具體的次序，類似于最優二叉查找樹，就是要記錄動态規劃産生的過程，略

----------------------------------------------------------------------------------------------

總結：

矩陣連乘問題是個卡特蘭數問題

其動态規劃的構造過程非常類似于最優二叉查找樹

矩陣連乘的最有子結構是什麼？

本文轉自農夫山泉别墅部落格園部落格，原文連結：http://www.cnblogs.com/yaowen/p/4466268.html，如需轉載請自行聯系原作者