Matrix-Chain Product,矩阵连乘问题

Last Updated: 2024-03-25 14:15:01 Monday

-- TOC --

矩阵乘法支持结合律的(associative),比如计算ABC,可以(AB)C,也可以A(BC)。不同的计算顺序,结果一样,但是计算量却很不同。矩阵连乘问题,就是寻找最小计算量的计算方法。

问题分析

比如有两个矩阵做乘法,\(A_{p,q}\cdot B_{q,r}=C_{p,r}\),完成这个矩阵乘法,共计算了\(pqr\)次scale乘法。当有一串矩阵连乘时,\(A_1A_2...A_n\),如何组合才能够让总的scale乘法量最小,这也是性能最好的矩阵乘法顺序。

比如计算:\(A_{10,100}B_{100,5}C_{5,50}\)

如果先算AB,总计算量为10*100*5+10*5*50=7500

如果先算BC,总计算量为100*5*50+10*100*50=75000

都是计算3个矩阵相乘,前者比后者快10倍。

输入是一个list,矩阵的dimension list,长度刚好比矩阵数量多1。

Subproblems

How to discern subproblems?

此问题不能使用In or Out的思路来构建子问题的递归,比如ABCD,A与B有两种可能,AB,或没有AB,当没有AB的时候,我们无法计算出A(的值,最右边的那个参数是缺失的。此时,只能使用Cut and Paste思路,将问题划分成左右两个subproblems,然后分别求解,最后再计算合并之后的值。

递归

一串矩阵连乘,可以考虑在中间任意一个位置划开,形成两串矩阵,这两串矩阵就是两个子问题。分别对这两个子问题递归,然后两串矩阵最后的解做最后的乘法,最后再选出计算量最小的那一个。代码如下:

def mcp(mc,i,j):
    if i == j-1:
        return 0
    lst = []
    for k in range(i+1,j):
        n = mcp(mc, i, k) \
                + mcp(mc, k, j) \
                + mc[i]*mc[k]*mc[j]
        lst.append(n)
    return min(lst)

分析一下复杂度:

$$T(n)=\sum_{i=1}^n\left(T(i)+T(n-i)\right)+1$$

显然\(O(2^n)\)

Dynamic Programming

Top-Down

class MatrixChain():

    def __init__(self, dlst):
        self.dlst = dlst
        self.dd = {}

    def mcp(self, i, j):
        if (i,j) in self.dd:
            return self.dd[i,j]
        if i == j-1:
            return 0
        lst = []
        for k in range(i+1,j):
            n = self.mcp(i, k) \
                 + self.mcp(k, j) \
                 + self.dlst[i] * self.dlst[k] * self.dlst[j]
            lst.append(n)
        self.dd[i,j] = min(lst)
        return self.dd[i,j]

一共有多少个subproblem?

$$T(n)=C_n^2=\Theta(n^2)$$

如果i和j是子问题最左边和最右边矩阵的编号,\(1\le i \le j\),每一对i和j,都对应一个子问题。

Bottom-Up

def mcp_bu(mc):
    size = len(mc) - 1
    T = [[0]*size for _ in range(size)]
    for i in range(size-1):
        T[i][i+1] = mc[i] * mc[i+1] * mc[i+2]
    for d in range(2,size):
        for i in range(size-d):
            assert T[i][i+d-1] != 0
            assert T[i+1][i+d] != 0
            a = T[i][i+d-1] + mc[i]*mc[i+d]*mc[i+d+1]
            b = T[i+1][i+d] + mc[i]*mc[i+1]*mc[i+d+1]
            T[i][i+d] = min(a,b)
    return T[0][size-1]

用ABCDE这5个矩阵连乘举例:

1. AB, BC, CD, DE
2. 
(AB)C or A(BC),
(BC)D or B(CD),
(CD)E or C(DE),
3.
(ABC)D or A(BCD),
(BCD)E or B(CDE),
4.
(ABCD)E or A(BCDE)

如何加括号

到底要如何加括号才能实现最小计算量,代码中还要加点东西,记录下来每次抉择的位置信息。具体就是记录下来每一对i和j所对应的最优的k的位置,在整个计算完成之后,用这个信息把所有加括号的位置找出来。代码略。

本文链接:https://cs.pynote.net/ag/dp/202403081/

-- EOF --

-- MORE --