矩阵链乘法和动态规划 _矩阵链乘法

本文概述

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

这是动态规划下的一种方法, 其中以前的输出用作下一个的输入。
在这里, 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。
可以通过两种方式将三个矩阵相乘：

A1, （A2, A3）：首先相乘（A2和A3）, 然后相乘并与A1求和。
（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。
动态规划算法的发展

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

动态规划方法令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标量乘法, 我们得到