matrix_chain_product

Matrix chain multiplication §

• 虽然矩阵乘法满足结合律，但是以不同方式结合，总的计算量不同，因此问题是以何种方式结合，能使得总计算量最小

• Ref: Wiki，【算法导论】动态规划之矩阵链乘法 来自Wiki的伪代码：

  // Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..n
  MatrixChainOrder(int dims[])
  {
      // length[dims] = n + 1
      n = dims.length - 1;
      // m[i,j] = Minimum number of scalar multiplications (i.e., cost)
      // needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]
      // The cost is zero when multiplying one matrix
      for (i = 1; i <= n; i++)
          m[i, i] = 0;
  
      for (len = 2; len <= n; len++) { // Subsequence lengths
          for (i = 1; i <= n - len + 1; i++) {
              j = i + len - 1;
              m[i, j] = MAXINT;
              for (k = i; k <= j - 1; k++) {
                  cost = m[i, k] + m[k+1, j] + dims[i-1]*dims[k]*dims[j];
                  if (cost < m[i, j]) {
                      m[i, j] = cost;
                      s[i, j] = k; // Index of the subsequence split that achieved minimal cost
                  }
              }
          }
      }
  }
  

• 若有矩阵和，假设为，为 则矩阵乘法的计算代价为，即次数值乘法（每次行列相乘再相加，共 / 次乘法，得到矩阵的一个元素，共行，列）

• 假设有矩阵链乘积 维度为

  Matrix	Dimension

  • 用矩阵m代表计算代价，m[i][j]为从第i个矩阵到第j个矩阵的最小代价 用矩阵s代表所选择的划分位置 如m[5][6]为 假设为矩阵链的长度，i为最左端的矩阵的行向量数，j为最右端的矩阵的列向量数，k为一个链化为两部分后中间过程中左侧矩阵的列向量数/右侧矩阵的行向量数

    1. 初始化时将m中所有元素设置成可能的最大值

    2. （）某个矩阵自身不需要进行乘法运算，计算代价为0，m[i][i]=0

    3. （）两个相邻矩阵，只需直接进行乘法即为其最小代价（动态规划中的最小问题）

       • m[i][j]=，如m[5][6]=，其中（i=5, j=i+l-1=5, k={5}）
       • s[i][j]没有什么可以选择的余地，s[i][j]=k

       m → i ↓ j	1	2	3	4	5	6
       6					5,000	0
       5				1,000	0
       4			750	0
       3		2,625	0
       2	15,750	0
       1	0

       s → i ↓ j	1	2	3	4	5	6
       6					5	x
       5				4	x
       4			3	x
       3		2	x
       2	1	x
       1	x

    4. （）此时需要用到的结果并进行一步计算，接着进行一次判断，如比较与 m[i][j]=m[i][k]+m[k+1][j]+，即计算左半部分的乘法数量，右半部分的乘法数量，及左右相乘时的乘法数量 回顾上一步，若，则m[i][k]=0，m[k+1][j]=0 若计算，则i=4, j=6, k={4, 5}

       • k=4时检查，k=5时检查 前者乘法次数为，后者乘法次数为 更新后m[4][6]=3500, s[4][6]=5

    5. 如此更新至时结束，即i=1, j=6

       m → i ↓ j	1	2	3	4	5	6
       6	15,125	10,500	5,375	3,500	5,000	0
       5	11,875	7,125	2,500	1,000	0
       4	9,375	4,375	750	0
       3	7,875	2,625	0
       2	15,750	0
       1	0

       s → i ↓ j	1	2	3	4	5	6
       6	3	3	3	5	5	x
       5	3	3	3	4	x
       4	3	3	3	x
       3	1	2	x
       2	1	x
       1	x

    6. 结果为