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

จากวิกิพีเดีย สารานุกรมเสรี

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 ตัว A1A2…An ต้องการหาลำดับการคูณแมทริกซ์ ที่ใช้จำนวนครั้งของการคูณน้อยที่สุด

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

ตามลำดับ

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

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

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

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

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)

[https://www.youtube.com/watch?v=GMzVeWpyTN0 1][https://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/ 1]
อ้างอิงผิดพลาด: มีป้ายระบุ <ref> สำหรับกลุ่มชื่อ "https://www.youtube.com/watch?v=GMzVeWpyTN0" แต่ไม่พบป้ายระบุ <references group="https://www.youtube.com/watch?v=GMzVeWpyTN0"/> ที่สอดคล้องกัน หรือไม่มีการปิด </ref>
อ้างอิงผิดพลาด: มีป้ายระบุ <ref> สำหรับกลุ่มชื่อ "https://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/" แต่ไม่พบป้ายระบุ <references group="https://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/"/> ที่สอดคล้องกัน หรือไม่มีการปิด </ref>