問題描述

給定n個矩陣：A1,A2,...,An，其中Ai與Ai+1是可乘的，i=1，2...，n-1。確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少。

矩陣乘法的順序安排

對于圖像處理來說，矩陣運行是中必不可少的重要數(shù)學方法，另外在神經(jīng)網(wǎng)絡、模式識別等領域也有著廣泛的用途。在這里就先來簡單復習一下矩陣的相關知識：

矩陣乘法

在矩陣乘法中，第一個矩陣的行數(shù)和第二個矩陣的列數(shù)必須是相同的。先來看一個簡單的例子：

之所以這樣要求，是因為矩陣的乘法定義中，就要求了，第一個矩陣每一行和第二個矩陣每一列相對應位置的數(shù)字做乘的操作：

如果A矩陣是p×q的矩陣，B是q×r的矩陣，那么乘積C是p×r的矩陣。它們一共計算了p×q×r次。

以下是一段計算兩個矩陣乘積的標準算法：

void matrixMultiply(int[][] matrixA, int[][] matrixB,int[][] matrixC,int ra, int ca, int rb, int cb) {
    if (ca != cb) {
        System.err.println("矩陣不可乘！");
        return;
    }   // end if

    for (int i = 0; i < ra; i++) {
        for (int j = 0; j < cb; j++) {
            int sum = matrixA[i][0] * matrixB[0][j];
            for (int k = 0; k < ca; k++) {
                sum += matrixA[i][k] * matrixB[k][j];
            }   // end for
            matrixC[i][j] = sum;
        }
    }
}

順序安排

假設給定3個矩陣，A、B、C，它們的規(guī)模分別是10×100、100×5和5×50。

• 如果按照((AB)C)的順序計算：
  為計算AB（規(guī)模10×5），需要做10×100×5=5000次標量乘法，再與C相乘又需要做10×5×50=2500次標量乘法， 共需要7500次標量乘法。
• 如果按照(A(BC))的順序計算：
  為計算BC（規(guī)模100×50），需要做100×5×50=25000次標量乘法，再與A相乘又需要做10×100×50=50000次標量乘法，共需要75000次標量乘法。

因此，按第一種順序計算矩陣連乘要比第二種順序快10倍。所以，進行一些計算來確定最有順序還是值得的。

動態(tài)規(guī)劃法

設m_Left,Right是進行矩陣乘法A_LeftA_Left+1···A_Right-1A_Right所需要的乘法次數(shù)。為一致起見，m_Left,Left=0。設最后的乘法是（A_Left···A_i）（A_i+1A_Right），其中 Left ≤ i ≤ Right。

此時所用的乘法次數(shù)為：m_Left,i + m_i+1,Right + c_Left-1c_ic_Right。這三項分別代表計算（A_Left···A_i）、（A_i+1A_Right）以及它們的乘積所需要的乘法。除了最后的答案，還要顯示實際的乘法順序，所以我們還要記錄i的值，由此得到以下算法：

public static void optMatrix(int[] c, long[][] m, int[][] lastChange) {
    int n = c.length - 1;

    for (int left = 0; left < n; left++) {
        m[left][left] = 0;
    }
    for (int k = 1; k <= n; k++) {
        for (int left = 1; left <= n - k; left++) { // k is right - left，即子問題規(guī)模
            // For each postion
            int right = left + k;
            m[left][right] = INFINITY;              // 置為無窮大
            for (int i = left; i < right; i++) {    // i為斷開位置
                long thisCost = m[left][i] + m[i + 1][right] +
                        c[left - 1] * c[i] * c[right];

                if (thisCost < m[left][right]) {    // Update min
                    m[left][right] = thisCost;
                    lastChange[left][right] = i;
                }
            }
        }   // end inner for
    }   // end outer for
}

這個程序包含三重嵌套循環(huán)，容易看出它以O(N³)時間運行。這里其實有更快地算法，但由于執(zhí)行具體矩陣乘法的時間仍然很可能會比計算最有順序的乘法的時間多得多，所以這個算法還是挺實用的。

歡迎轉(zhuǎn)載，轉(zhuǎn)載請注明出處！
簡書ID：@我沒有三顆心臟
github：wmyskxz
歡迎關注公眾微信號：wmyskxz_javaweb
分享自己的Java Web學習之路以及各種Java學習資料