Question:
Consider the matrices A1, A2, A3 and A4, of sizes: 2 15, 15 10, 10 1 and 1 20, respectively.
(1) If B is a matrix of size 10 15, can the following matrix multiplications be performed, and if so, what will be the size of the matrix obtained as a result of the multiplication?
A2 B and B A3.
(2) Using dynamic programming approach, find the minimum number of multiplications necessary to compute the product of matrices:
A1 ´ A2 ´ A3 ´ A4.
Indicate the corresponding optimal position of brackets.
Answer:
(1)
A2B = 15*15
BA3: Error.
(2)
# -*- coding: utf-8 -*-
class Matrix:
def __init__(self, row_num=0, col_num=0, matrix=None):
if matrix != None:
self.row_num = len(matrix)
self.col_num = len(matrix[0])
else:
self.row_num = row_num
self.col_num = col_num
self.matrix = matrix
def matrix_chain(matrixs):
matrix_num = len(matrixs)
count = [[0 for j in range(matrix_num)] for i in range(matrix_num)]
flag = [[0 for j in range(matrix_num)] for i in range(matrix_num)]
for interval in range(1, matrix_num + 1):
for i in range(matrix_num - interval):
j = i + interval
count[i][j] = count[i][i] + count[i + 1][j] + matrixs[i].row_num * matrixs[i + 1].row_num * matrixs[j].col_num
flag[i][j] = i
for k in range(i + 1, j):
temp = count[i][k] + count[k + 1][j] + matrixs[i].row_num * matrixs[k + 1].row_num * matrixs[j].col_num
if temp < count[i][j]:
count[i][j] = temp
flag[i][j] = k
traceback(0, matrix_num - 1, flag)
return count[0][matrix_num - 1]
def traceback(i, j, flag):
if i == j:
return
if j - i > 1:
print(str(i + 1) + '~' + str(j + 1), end=': ')
print(str(i + 1) + ":" + str(flag[i][j] + 1), end=',')
print(str(flag[i][j] + 2) + ":" + str(j + 1))
traceback(i, flag[i][j], flag)
traceback(flag[i][j] + 1, j, flag)
matrixs = [Matrix(2, 15), Matrix(15, 10), Matrix(10, 1), Matrix(1, 20)]
result = matrix_chain(matrixs)
print(result)
The result is 220
Reference: https://www.jb51.net/article/129168.htm