矩阵链乘法和动态规划

本文概述

• 动态规划算法的发展
• 动态规划方法

这是动态规划下的一种方法, 其中以前的输出用作下一个的输入。

在这里, Chain表示一个矩阵的列等于第二个矩阵的行（总是）。

一般来说：

If A = ⌊aij⌋ is a p x q matrix 
   B = ⌊bij⌋ is a q x r matrix
   C = ⌊cij⌋ is a p x r matrix

然后

给定以下矩阵{A1, A2, A3, … An}, 我们必须执行矩阵乘法, 这可以通过一系列矩阵乘法来完成

A1 xA2 x, A3 x.....x An

矩阵乘法运算本质上是关联的, 而是可交换的。这样, 我们的意思是我们必须遵循上述矩阵顺序进行乘法运算, 但是我们可以根据需要随意在上面的括号中加上括号。

通常, 对于1≤i≤p和1≤j≤r

可以看到, 矩阵“ C”中的总条目为“ pr”, 因为矩阵的维数为pxr。每个条目也需要O（q）次来计算, 因此计算矩阵“ C”的所有可能条目的总时间’是’A’和’B’的乘积, 与尺寸pq r的乘积成比例。

还应注意, 我们可以通过对括号重新排序来节省操作数。

例1：让我们有3个矩阵, 分别为（10 x 100）, （100 x 5）和（5 x 50）的A1, A2, A3。

可以通过两种方式将三个矩阵相乘：

1. A1, （A2, A3）：首先相乘（A2和A3）, 然后相乘并与A1求和。
2. （A1, A2）, A3：首先相乘（A1和A2）, 然后相乘并与A3求和。

情况1中的标量乘法数将为：

(100 x 5 x 50) + (10 x 100 x 50) = 25000 + 50000 = 75000

情况2中的标量乘法数将为：

(100 x 10 x 5) + (10 x 5 x 50) = 5000 + 2500 = 7500

为了找到最佳的计算乘积的方法, 我们可以简单地用各种可能的方式对表达式加上括号, 并在每次需要多少个标量乘法时计数。

矩阵链乘法问题可以表述为“找到要相乘的矩阵链的最佳括号, 以使标量乘法的数量最小化”。

对矩阵加括号的方式数目：

有很多方法可以对这些矩阵进行括号括起来。如果有n个项, 则可以通过（n-1）种方式放置最外面的一对括号。

(A1) (A2, A3, A4, ................An)
Or (A1, A2)  (A3, A4 .................An)
Or (A1, A2, A3)  (A4 ...............An)
........................ 
Or(A1, A2, A3.............An-1) (An)

可以看出, 在分解第k个矩阵之后, 我们剩下两个带括号的矩阵序列：一个由“ k”个矩阵组成, 另一个由“ n-k”个矩阵组成。

现在有“ L”种括号左子列表的方式和“ R”种括号右子列表的方式, 那么Total将为L.R：

另外p（n）= c（n-1）, 其中c（n）是第n个Catalon数

c（n）=

在应用斯特林公式时, 我们有

c（n）=Ω

这表明4n增长更快, 因为它是指数函数, 然后是n1.5。

动态规划算法的发展

1. 表征最佳解决方案的结构。
2. 递归定义最佳解决方案的值。
3. 以自下而上的方式计算最佳解决方案的价值。
4. 根据计算的信息构造最佳解决方案。

动态规划方法

令Ai, j为矩阵i与j相乘的结果。可以看出, Ai, j的维数是pi-1 x pj矩阵。

动态规划解决方案涉及将问题分解为多个子问题, 这些子问题的解决方案可以组合起来解决全局问题。

在最大括号内, 我们将两个矩阵相乘

A1.....n=A1....k x Ak+1....n)

因此, 我们剩下两个问题：

• 如何拆分矩阵序列？
• 如何在子序列A1 ….. k和Ak + 1 … n中加上括号？

对于找到“ k”的最佳值的第一个问题, 一个可能的答案是检查所有“ k”的可能选择, 并考虑其中的最佳选择。但是可以看出, 检查所有可能性将导致总可能性成指数增长。还可以注意到, 仅存在O（n2）个不同的矩阵序列, 以这种方式无法达到指数增长。

步骤1：最优括号的结构：我们在动态范例中的第一步是找到最优子结构, 然后使用它来构造从最优解到子问题的最优解。

设Ai …. j, 其中i≤j表示评估乘积所得的矩阵

Ai Ai + 1 …. Aj。

如果i <j, 则乘积Ai Ai + 1 ………… Aj的任何括号都必须在i≤k≤j范围内的某个整数k处将乘积在Ak和Ak + 1之间进行分割。也就是说, 对于k的某个值, 我们首先计算矩阵Ai ….. k和Ak + 1 …. j, 然后将它们相乘以生成最终乘积Ai …. j。计算Ai …. k的成本加上计算Ak + 1 …. j的成本加上将它们相乘的成本就是括号的成本。

步骤2：递归解：令m [i, j]为计算matrixAi …. j所需的最小标量乘法数。

如果i = j, 则链仅由一个矩阵Ai …. i = Ai组成, 因此不需要标量乘法即可计算乘积。因此, 对于i = 1、2、3 … n, m [i, j] = 0。

如果i <j, 我们假定为使产品具有最佳括号, 我们将其在Ak和Ak + 1之间划分, 其中i≤k≤j。然后, m [i, j]等于计算子乘积Ai …. k和Ak + 1 …. j +将它们相乘的成本的最小成本。我们知道Ai的维数为pi-1 x pi, 因此计算乘积Ai …. k和Ak + 1 …. jtakes pi-1 pk pj标量乘法, 我们得到

m [i, j] = m [i, k] + m [k + 1, j] + pi-1  pk pj

“ k”只有（j-1）个可能的值, 即k = i, i + 1 ….. j-1。由于最佳括号必须为“ k”使用这些值之一, 因此我们只需检查所有值即可找到最佳值。

因此, 将产品Ai Ai + 1 …… Aj括起来的最小成本变为

要构建最优解, 让我们将s [i, j]定义为’k’的值, 在该值处我们可以对乘积Ai Ai + 1 ….. Aj进行拆分以获得最优括号, 即s [i, j] = k使得

m [i, j] = m [i, k] + m [k + 1, j] + pi-1  pk pj