矩阵链乘积

矩阵链乘积（英语：Matrix chain multiplication，或Matrix Chain Ordering Problem，MCOP）是可用动态规划解决的最佳化问题。给定一序列矩阵，期望求出相乘这些矩阵的最有效方法。此问题并不是真的去执行其乘法，而只是决定执行乘法的顺序而已。

因为矩阵乘法具有结合律，所有其运算顺序有很多种选择。换句话说，不论如何括号其乘积，最后结果都会是一样的。例如，若有四个矩阵ABCD，将可以有：

ABCD=(AB)(CD)=A(BCD)=A(BC)D=…

但括号其乘积的顺序是会影响到需计算乘积所需简单算术运算的数目，即其效率。例如，设A为一10 X 30矩阵，B为30 X 5矩阵与C为5 X 60矩阵，则：

明显地，第一种方式要有效多了。既然已确认过此问题了，那要如何决定n个矩阵相乘的最佳顺序呢？可以比较每一顺序的运算量（使用蛮力），但这将需要时间O(2n)，是一种非常慢且对大n不实在的方法。那解决方法，如我们将看到的，是将问题分成一套相关的子问题。以解答子问题一次而再使用其解答数次，即可以彻底地得出其所需时间。此一方法称为动态规划。

N个矩阵（A1，A2，A3，，，An）链乘的最佳顺序，对于这个问题，它的子问题是什么？如何将它拆分成更小的子问题呢？

可以将这N个矩阵分成两部分，第一部分的最佳顺序是一个子问题，第二部分的最佳顺序也是一个子问题。那这两个子问题和大问题又如何建立联系呢？

将N个矩阵分成两部分，有多种不同的划分方法，三个矩阵链乘有2种划分方法：（AB）C和A（BC）

我们去尝试所有的划分方法，求得每种划分方法需要的计算数，取最小的作为N个矩阵链乘的最优解。

划分而得的两部分又可以拆分成更小的子问题，这时候动态规划就能发挥威力，我们自下而上去求解，将求得的结果存在一张表中，方便复用。

由此可见，动态规划问题的主要求解思路就是如何寻找最优解问题的子问题，以及如何将大问题和子问题联系起来。

一些输入：

** Matrix-chain product. The following are some instances.

a) <3, 5, 2, 1,10>

b) <2, 7, 3, 6, 10>

c) <10, 3, 15, 12, 7, 2>

d) <7, 2, 4, 15, 20, 5>

package main

import (
   "fmt"
   "math"
)

const INFINITY = math.MaxInt64

func main() {
   nums1 := []int{3, 5, 2, 1, 10}
   //nums2 := []int{2, 7, 3, 6, 10}
   //nums3 := []int{10, 3, 15, 12, 7, 2}
   //nums4 := []int{7, 2, 4, 15, 20, 5}
   MatrixChainMultiplication(nums1)
   //MatrixChainMultiplication(nums2)
   //MatrixChainMultiplication(nums3)
   //MatrixChainMultiplication(nums4)
}

// 输出最优解和计算次数
func MatrixChainMultiplication(p []int) {
   // 矩阵个数为 len(p) - 1
   n := len(p) - 1

   // m[i][j]表示第i个矩阵到第j个矩阵进行矩阵链乘的最小计算数
   m := make([][]int, n+1)
   for i := range m {
      m[i] = make([]int, n+1)
   }
   // s[i][j]表示使得 第i个矩阵到第j个矩阵进行矩阵链乘的计算数最小 的分割点
   s := make([][]int, n+1)
   for i := range s {
      s[i] = make([]int, n+1)
   }

   for l := 2; l <= n; l++ { // l：chain length
      for i := 1; i <= n-l+1; i++ {
         j := i + l - 1
         m[i][j] = INFINITY
         for k := i; k <= j-1; k++ {
            q := m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
            if q < m[i][j] {
               m[i][j] = q
               s[i][j] = k
            }
         }
      }
   }

   fmt.Println("矩阵M：")
   for _, v := range m {
      fmt.Println(v)
   }
   fmt.Println("矩阵链乘的最小计算数：", m[1][n])
   fmt.Println("----------------------")
   fmt.Println("矩阵S：")
   for _, v := range s {
      fmt.Println(v)
   }
   fmt.Println("使得矩阵链乘计算数最小的计算次序：")
   displayPriority(s, 1, n)
}

// 根据断点位置递归的去加括号
func displayPriority(s [][]int, i, j int) {
   if i == j {
      fmt.Printf("A%d", i)
   } else {
      fmt.Print("(")
      displayPriority(s, i, s[i][j])
      displayPriority(s, s[i][j]+1, j)
      fmt.Print(")")
   }
}