矩陣連乘

問(wèn)題定義

  • 輸入：給定n個(gè)矩陣，矩陣間連乘

    a1 ... an : ai 與 ai + 1 可乘

    令a1：p0 * p1

      ...

    an：pn-1 * pn

    則：輸入用一維數(shù)組表示，P:{p0p1p2...pn}

  • 輸出：求最少乘法次數(shù)的計(jì)算方法

    • 特征：無(wú)論在哪里斷開(kāi)，分開(kāi)部分的矩陣作為一個(gè)整體不影響整個(gè)矩陣的連乘

    • 對(duì)于矩陣序列，不同的乘次序?qū)?dǎo)致不同的乘法次數(shù)

    • 例如：a1 * a2 * a3的乘法次數(shù)

      (a1 * a2) * a3 ：(p0 * p1 * p2) + (p0 * p2 * p3)

      a1 * (a2 * a3)：(p1 * p2 * p3) + (p0 * p1 * p3)

    • 找出最優(yōu)計(jì)算次序以使得矩陣連乘所需要的計(jì)算次數(shù)最少

蠻力法

枚舉每一種劃分括號(hào)的情況，計(jì)算出他們的乘法次數(shù)，取最小的劃分情況

A1A2A3...An：添加括號(hào)，直到只有一個(gè)矩陣可以加括號(hào)，然后計(jì)算他們的連乘次數(shù)

A1(A2(A3...An))的連乘次數(shù)：p2 * ... * pn + p1 * p3 * pn + p0 * p1 * pn

遞歸分治

優(yōu)化暴力枚舉（用k表示分割的位置）

每次調(diào)用遞歸式時(shí)：傳入分割后的矩陣列

遞歸出口：當(dāng)傳入的矩陣列中只有一個(gè)矩陣，返回0

回溯處理：計(jì)算兩邊分割乘法次數(shù)的和，計(jì)算兩邊合并的乘法次數(shù)再相加，取某個(gè)分割位置k時(shí)的最小值
遞歸式： F(1,n) = \begin{cases} \sum_{k=1}^n(min{F(1,k)} + F(k+1, n) + P_0 \times P_k \times P_n), &\ n\ \gt\ 1\\ 0, &\ n\ = 1\\ \end{cases}

  • 優(yōu)點(diǎn)：存在子問(wèn)題最優(yōu)解
  • 缺點(diǎn)：存在重復(fù)計(jì)算部分
    • 為什么
      1. 遞歸使用幀無(wú)法保存太多的信息
      2. 子問(wèn)題重疊，因?yàn)椴煌牟糠謩澐挚赡苡上嗤淖訂?wèn)題組成，那么遞歸調(diào)用中出現(xiàn)重復(fù)計(jì)算的子問(wèn)題是隨著遞歸深度變化的

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

  • 使用空間換時(shí)間，將子問(wèn)題記錄下來(lái)

    • 那么就將遞歸分治的缺點(diǎn)改為優(yōu)點(diǎn)，這下子，解決方法就是利用了動(dòng)態(tài)規(guī)劃的思想

  • 令 m(i,j) ：為i，j之間的矩陣列的最小乘法次數(shù)，在這之間使用k作為劃分的位置

    • m(i,j) = \begin{cases} \sum_{k=i}^j(min{F(i,k)} + F(k+1, j) + P_{i-1} \times P_k \times P_n), &\ i\ \lt\ j\\ 0, &\ i\ = j\\ \end{cases}

    • 根據(jù)上述定義，二維表m的對(duì)角線上都是0，m(1,n)是我們需要的最少乘法次數(shù)

  • 令s(i,j)：為i，j之間矩陣列的最優(yōu)分割位置

  • 時(shí)間復(fù)雜度：

    • for(1 to n)：枚舉序列長(zhǎng)度

      • for(0 to r)：枚舉矩陣子列的起點(diǎn)

        • j = r

          for(k = i + 1 to j)：枚舉矩陣子序列分割點(diǎn)

          s表記錄最優(yōu)的分割位置、m表最少乘法次數(shù)

    • 線性時(shí)間讀s表，構(gòu)造最優(yōu)矩陣連乘的計(jì)算步驟

import java.util.Arrays;

public class MatrixChainTest {

    /**
     * @param p：矩陣維數(shù)序列，其長(zhǎng)度減一為連乘矩陣的個(gè)數(shù)
     * @param memory：ai*...*aj的最小數(shù)乘次數(shù)
     * @param s：最佳括號(hào)斷開(kāi)位置
     * 操作數(shù)組時(shí)，從下標(biāo)開(kāi)始
     */
    public static void matrixChain(int[] p, int[][] memory, int[][] s) {
        int n = p.length - 1;//矩陣個(gè)數(shù)
        //初始狀態(tài)對(duì)角線置為0
        for(int i = 0; i < memory.length; i++) {
            memory[i][i] = 0;
        }
        //矩陣長(zhǎng)度從二(下標(biāo)0，1)開(kāi)始，計(jì)算不同子矩陣的數(shù)乘次數(shù)
        for(int r = 1; r < n; r++) {//r+1：矩陣列長(zhǎng)度
            for(int i = 0; i < n - r; i++) {//從第一個(gè)矩陣開(kāi)始，枚舉r+1長(zhǎng)度的矩陣列（的起點(diǎn)）
                int j = i + r;//矩陣列：A_(i+1)*...*A_(j+1)
                //矩陣列長(zhǎng)度：j - i + 1
                //斷開(kāi)位置(矩陣列的第幾個(gè)(從1開(kāi)始算)位置)與下標(biāo)關(guān)系：x_斷 = x_(下+1)
                //設(shè)最先斷開(kāi)的位置是A_(i+1)
                memory[i][j] = memory[i][i] + memory[i+1][j] + p[i] * p[i + 1] * p[j + 1];
                s[i][j] = i + 1;
                //枚舉斷開(kāi)位置，在矩陣列：A_(i+1)*...*A_(j+1)的從 i+2 到 j+1
                for(int k = i + 1; k < j; k++) {//斷開(kāi)位置從 k + 1開(kāi)始
                    int temp = memory[i][k] + memory[k+1][j] + p[i] * p[k + 1] * p[j + 1];
                    if(temp < memory[i][j]) {
                        memory[i][j] = temp;
                        s[i][j] = k + 1;
                    }
                }
            }
        }
        System.out.println("矩陣連乘的最少乘法次數(shù)為" + memory[0][n - 1]);
    }

    /**
     * 利用矩陣序列最優(yōu)的分割位置s，構(gòu)造最優(yōu)計(jì)算次序
     * @param s：最優(yōu)分割位置
     * @return：矩陣序列p的最優(yōu)計(jì)算次序
     */
    private static String matrixChainMake(int[][] s) {
        int n = s.length;
        String[] temp = new String[n];
        //矩陣序列初始化
        for(int i = 0; i < n; i++) {
            temp[i] = "A" + i;
        }
        //加括號(hào)
        for(int i = 0; i < n - 2; i++) {
            int k = s[i][n - 1];//獲得分割的位置
            if(k - i > 1) {//括號(hào)包住兩個(gè)以上的矩陣列
                temp[i] = "(" + temp[i];
                temp[k - 1] += ")";
            }
            if(n - k > 1) {
                temp[k] = "(" + temp[k];
                temp[n - 1] += ")";
            }
        }
        //最后答案處理
        StringBuilder rs = new StringBuilder();
        for(int i = 0; i < temp.length; i++) {
            rs.append(temp[i]);
        }
        System.out.println("最優(yōu)計(jì)算次序?yàn)椋? + rs.toString());
        return rs.toString();
    }

    /**
     *外部調(diào)用入口
     * @param p：矩陣列的維數(shù)
     * @return 返回矩陣連乘的最優(yōu)計(jì)算次序
     */
    public static String matrixChain(int[] p) {
        int[][] m = new int[p.length - 1][p.length - 1];
        int[][] s = new int[p.length - 1][p.length - 1];
        MatrixChainTest.matrixChain(p, m, s);
        System.out.println("m：");
        array2dShow(m);
        System.out.println("s：");
        array2dShow(s);
        return matrixChainMake(s);
    }

    public static void main(String[] args) {
        int[] p = {30, 35, 15, 5, 10, 20, 25};
        matrixChain(p);
    }

    private static void array2dShow(int[][] s) {
        for(int i = 0; i <s.length; i++) {
            System.out.println(Arrays.toString(s[i]));
        }
    }

}

相關(guān)鏈接：

學(xué)習(xí)別人的思想，總結(jié)自己的想法：

  • 分析一個(gè)問(wèn)題的解決方法，很容易想到暴力，然后再想著優(yōu)化，發(fā)現(xiàn)問(wèn)題可以被分割成獨(dú)立的子問(wèn)題，例如這題就朝分治遞歸去了；再分析遞歸分治的過(guò)程，發(fā)現(xiàn)存在重復(fù)計(jì)算的子問(wèn)題，那么出現(xiàn)了動(dòng)態(tài)規(guī)劃問(wèn)題的特性：最優(yōu)子結(jié)構(gòu)、子問(wèn)題重疊
  • 一步步的分析才能得到結(jié)果，不是觀測(cè)就來(lái)的

動(dòng)態(tài)規(guī)劃基本步驟：
1.找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。
2.遞歸地定義最優(yōu)值。
3.以自底向上的方式計(jì)算出最優(yōu)值。
4.根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容