การคูณลูกโซ่ของเมทริกซ์

การคูณลูกโซ่ของเมทริกซ์ (อังกฤษ: Matrix chain multiplication) ใช้สำหรับการแก้ปัญหาการคูณ matrix ซึ่งการคูณปกติอาจจะมีจำนวนครั้งมากเกินไปหรือมีประสิทธิภาพที่ไม่ดีพอซึ่งการใช้ algorithm นี้เป็นการคูณ matrix อย่างต่อเนื่องเพื่อหารูปแบบการคูณที่ดีที่สุดโดยใช้คุณสมบัติการเปลี่ยนหมวดหมู่การคูณของ matrix

ตัวอย่าง

matrix X มีขนาด 10 x 3

matrix Y มีขนาด 3 x 5

matrix Z มีขนาด 5 x 6 จำนวนครั้งของการคูณแบบ (X * Y) * Z คือ

(10*3*5 + 10*5*6) = 450 ครั้ง

ส่วนจำนวนครั้งของการคูณแบบ X * (Y * Z) คือ (3*5*6 + 10*3*6) = 270 ครั้ง จะเห็นได้ว่าการเปลี่ยนหมวดหมู่การคูณช่วยเพิ่มประสิทธิภาพหรือลดจำนวนครั้งการคูณลงได้ เราจึงต้องหารูปแบบของหมวดหมู่ที่ดีที่สุดโดยใช้ Matrix-Chain-Multiplication ทำการคูณ

ถ้าเราต้องการคูณแมทริกซ์จำนวน n ตัว A₁A₂…A_n ต้องการหาลำดับการคูณแมทริกซ์ ที่ใช้จำนวนครั้งของการคูณน้อยที่สุด

เช่น n = 3 ต้องการคูณ A₁A₂A₃ เมื่อ A₁, A₂, A₃ มีขนาด10x100, 100x5, และ 5x50

ตามลำดับ

(A₁A₂)A₃) ต้องใช้จำนวนครั้งของการคูณ = 10*100*5 เพื่อคำนวณ (A₁A₂)+ 10*5*50 เพื่อคำนวณ ((A₁A₂)A₃)=7,500 ครั้ง

(A₁(A₂A₃)) ต้องใช้จำนวนครั้งของการคูณ = 100*5*50 เพื่อคำนวณ (A₂A₃)

+ 10*100*50 เพื่อคำนวณ (A₁(A₂A₃)) = 75,000 ครั้ง

จะเห็นได้ว่า ((A₁A₂)A₃) ใช้จำนวนครั้งของการคูณน้อยกว่า (A₁(A₂A₃))ถึงสิบเท่า

import sys
 
# Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
def MatrixChainOrder(p, n):
    # For simplicity of the program, one extra row and one
    # extra column are allocated in m[][].  0th row and 0th
    # column of m[][] are not used
    m = [[0 for x in range(n)] for x in range(n)] # O(n^2)
    # m[i,j] = Minimum number of scalar multiplications needed
    # to compute the matrix A[i]A[i+1]...A[j] = A[i..j] where
    # dimension of A[i] is p[i-1] x p[i]
    # cost is zero when multiplying one matrix.
    for i in range(1, n): #O(n) + O(n^2)
        m[i][i] = 0
    # L is chain length.
    for L in range(2, n): 
        for i in range(1, n-L+1):# O(n^2)
            j = i+L-1
            m[i][j] = float('inf')   #จำนวนเต็มบวกที่ใหญ่ที่สุดที่รองรับโดยจำนวนเต็มปกติของ Python นี่คืออย่างน้อย 2 ** 31-1 จำนวนเต็มลบที่ใหญ่ที่สุดคือ -maxint-1 - ผลลัพธ์ที่ไม่สมมาตรจากการใช้เลขคณิตไบนารีเสริมของ 2
            for k in range(i, j):# O(n^2)* O(n) = O(n^3)
                # q = cost/scalar multiplications
                q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
                if q < m[i][j]:
                    m[i][j] = q
 
    return m[1][n-1]
 
# Driver program to test above function
arr = [1, 2, 3 ,4]
size = len(arr)
 
print("Minimum number of multiplications is " +
       str(MatrixChainOrder(arr, size)))
# best case =  O(n^3)
# worst case = O(n^3)

อ้างอิง