31-完美图解

4.6.3　完美图解

现在我们假设有5个矩阵，如表4-1所示。

表4-1　矩阵的规模

| 矩阵 | A₁ | A₂ | A₃ | A₄ | A₅ | | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | | 规模 | 3×5 | 5×10 | 10×8 | 8×2 | 2×4 |

（1）初始化

采用一维数组p[]记录矩阵的行和列，实际上只需要记录每个矩阵的行，再加上最后一个矩阵的列即可，如图4-46所示。m[i][i]=0，s[i][i]=0，其中i= 1，2，3，4，5。

图4-46　记录行列的数组p[]

最优值数组m[i][i]=0，最优决策数组s[i][i]=0，其中i= 1，2，3，4，5。如图4-47所示。

图4-47　**m**[][]和**s**[][]初始化

（2）计算两个矩阵相乘的最优值

规模r=2。根据递归式：

• A₁*A₂：k=1，m[1][2]=min{ m[1][1]+ m[2][2]+p₀p₁p₂}=150；s[1][2]=1。
• A₂*A₃：k=2，m[2][3]=min{ m[2][2]+ m[3][3]+p₁p₂p₃}=400；s[2][3]=2。
• A₃*A₄：k=3，m[3][4]=min{ m[3][3]+ m[4][4]+p₂p₃p₄}=160；s[3][4]=3。
• A₄*A₅：k=4，m[4][5]=min{ m[4][4]+ m[5][5]+p₃p₄p₅}=64； s[4][5]=4。

计算完毕，如图4-48所示。

图4-48　**m**[][]和**s**[][]计算过程

（3）计算3个矩阵相乘的最优值

规模r=3。根据递归式：

• A₁*A*₂A**₃：

；

s[1][3]=2。

• A₂*A*₃A**₄：

；

s[2][4]=2。

• A₃*A*₄A**₅：

；

s[3][5]=4。

计算完毕，如图4-49所示。

图4-49　**m**[][]和**s**[][]计算过程

（4）计算4个矩阵相乘的最优值

规模r=4。根据递归式：

• A₁*A*₂A**₃*A₄：

；

s[1][4]=1。

• A₂*A*₃A**₄*A₅：

；

s[2][5]=4。

计算完毕，如图4-50所示。

图4-50　**m**[][]和**s**[][]计算过程

（5）计算5个矩阵相乘的最优值

规模r=5。根据递归式：

• A₁*A*₂A₃A₄A**₅：

；

s[1][5]=4。

计算完毕，如图4-51所示。

图4-51**m**[][]和**s**[][]计算过程

（6）构造最优解

根据最优决策数组s[][]中的数据来构造最优解，即加括号的位置。

首先读取s[1][5]=4，表示在k=4的位置把矩阵分为两个子问题：（A₁A₂A₃A₄）、A₅。

再看第一个子问题（A₁A₂A₃A₄），读取s[1][4]=1，表示在k=1的位置把矩阵分为两个子问题：A₁、（A₂A₃A₄）。

子问题A₁不用再分解，输出；子问题（A₂A₃A₄），读取s[2][4]=2，表示在k=2的位置把矩阵分为两个子问题：A₂、（A₃A₄）。

子问题A₂不用再分解，输出；子问题(A₃A₄)，读取s[3][4]=3，表示在k=3的位置把矩阵分为两个子问题：A₃、A₄。这两个子问题都不用再分解，输出。

子问题A₅不用再分解，输出。

最优解构造过程如图4-52所示。

图4-52　最优解构造过程

最优解为：（（A₁（A₂（A₃A₄）））A₅）。

最优值为：314。