问题定义
-
输入：给定n个矩阵，矩阵间连乘
a1 ... an : ai 与 ai + 1 可乘
令a1：p0 * p1
...an：pn-1 * pn
则：输入用一维数组表示，P:{p0p1p2...pn}
-
输出：求最少乘法次数的计算方法
特征：无论在哪里断开，分开部分的矩阵作为一个整体不影响整个矩阵的连乘
对于矩阵序列，不同的乘次序将导致不同的乘法次数
-
例如：a1 * a2 * a3的乘法次数
(a1 * a2) * a3 ：(p0 * p1 * p2) + (p0 * p2 * p3)
a1 * (a2 * a3)：(p1 * p2 * p3) + (p0 * p1 * p3)
找出最优计算次序以使得矩阵连乘所需要的计算次数最少
蛮力法
枚举每一种划分括号的情况，计算出他们的乘法次数，取最小的划分情况
A1A2A3...An：添加括号，直到只有一个矩阵可以加括号，然后计算他们的连乘次数
A1(A2(A3...An))的连乘次数：p2 * ... * pn + p1 * p3 * pn + p0 * p1 * pn
递归分治
优化暴力枚举（用k表示分割的位置）
每次调用递归式时：传入分割后的矩阵列
递归出口：当传入的矩阵列中只有一个矩阵，返回0
回溯处理：计算两边分割乘法次数的和，计算两边合并的乘法次数再相加，取某个分割位置k时的最小值
- 优点：存在子问题最优解
- 缺点：存在重复计算部分
- 为什么
- 递归使用帧无法保存太多的信息
- 子问题重叠，因为不同的部分划分可能由相同的子问题组成，那么递归调用中出现重复计算的子问题是随着递归深度变化的
- 为什么
动态规划法
-
使用空间换时间，将子问题记录下来
- 那么就将递归分治的缺点改为优点，这下子，解决方法就是利用了动态规划的思想
-
令 m(i,j) ：为i，j之间的矩阵列的最小乘法次数，在这之间使用k作为划分的位置
根据上述定义，二维表m的对角线上都是0，m(1,n)是我们需要的最少乘法次数
令s(i,j)：为i，j之间矩阵列的最优分割位置
-
时间复杂度：
-
for(1 to n)：枚举序列长度
-
for(0 to r)：枚举矩阵子列的起点
-
j = r
for(k = i + 1 to j)：枚举矩阵子序列分割点
s表记录最优的分割位置、m表最少乘法次数
-
-
线性时间读s表，构造最优矩阵连乘的计算步骤
-
import java.util.Arrays;
public class MatrixChainTest {
/**
* @param p：矩阵维数序列，其长度减一为连乘矩阵的个数
* @param memory：ai*...*aj的最小数乘次数
* @param s：最佳括号断开位置
* 操作数组时，从下标开始
*/
public static void matrixChain(int[] p, int[][] memory, int[][] s) {
int n = p.length - 1;//矩阵个数
//初始状态对角线置为0
for(int i = 0; i < memory.length; i++) {
memory[i][i] = 0;
}
//矩阵长度从二(下标0，1)开始，计算不同子矩阵的数乘次数
for(int r = 1; r < n; r++) {//r+1：矩阵列长度
for(int i = 0; i < n - r; i++) {//从第一个矩阵开始，枚举r+1长度的矩阵列（的起点）
int j = i + r;//矩阵列：A_(i+1)*...*A_(j+1)
//矩阵列长度：j - i + 1
//断开位置(矩阵列的第几个(从1开始算)位置)与下标关系：x_断 = x_(下+1)
//设最先断开的位置是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;
//枚举断开位置，在矩阵列：A_(i+1)*...*A_(j+1)的从 i+2 到 j+1
for(int k = i + 1; k < j; k++) {//断开位置从 k + 1开始
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("矩阵连乘的最少乘法次数为" + memory[0][n - 1]);
}
/**
* 利用矩阵序列最优的分割位置s，构造最优计算次序
* @param s：最优分割位置
* @return：矩阵序列p的最优计算次序
*/
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;
}
//加括号
for(int i = 0; i < n - 2; i++) {
int k = s[i][n - 1];//获得分割的位置
if(k - i > 1) {//括号包住两个以上的矩阵列
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("最优计算次序为：" + rs.toString());
return rs.toString();
}
/**
*外部调用入口
* @param p：矩阵列的维数
* @return 返回矩阵连乘的最优计算次序
*/
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]));
}
}
}
相关链接：
- 09_动态规划之矩阵连乘算法设计与分析哔哩哔哩_bilibili：推荐的讲解视频，前面的引入和后面的思维发散都很有趣，引人深思
- 矩阵连乘：和视频的讲解思路一致
- 动态规划之——矩阵连乘（全网最详细博文，看这一篇就够了！）：很详细，很尽心的博文（没代码纯思路，和视频讲解一样
学习别人的思想，总结自己的想法：
- 分析一个问题的解决方法，很容易想到暴力，然后再想着优化，发现问题可以被分割成独立的子问题，例如这题就朝分治递归去了；再分析递归分治的过程，发现存在重复计算的子问题，那么出现了动态规划问题的特性：最优子结构、子问题重叠
- 一步步的分析才能得到结果，不是观测就来的
动态规划基本步骤：
1.找出最优解的性质，并刻划其结构特征。
2.递归地定义最优值。
3.以自底向上的方式计算出最优值。
4.根据计算最优值时得到的信息，构造最优解。
