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

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) 

อ้างอิงผิดพลาด: มีป้ายระบุ <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>