연쇄 행렬 곱셈

문제점

• 행렬 곱셈의 순서에 따라서 각 원소의 곱셈 횟수가 달라짐
  ⁃ 각 원소의 곱셈 횟수가 가장 작아지도록 하는 곱셈 순서가 최적의 순서

• ex) 일반적으로, i × k 행렬과 k × j 행렬을 곱하면 i × j 행렬이 나옴
  ⁃ 원소 곱셈의 횟수: i × k × j

• 연쇄 행렬이 4개일 경우 다섯가지 경우의 수가 존재
  ⁃ A(B(CD)) = 3,680
  ⁃ (AB)(CD) = 8,880
  ⁃ A((BC)D) = 1,232
  ⁃ ((AB)C)D = 10,320
  ⁃ (A(BC))D = 3,120

python 코드

def minmult (d):
  n = len(d) - 1
  M = [[-1] * (n + 1) for _ in range(n + 1)]
  P = [[-1] * (n + 1) for _ in range(n + 1)]
  for i in range(1, n + 1):
    M[i][i] = 0
  for diagonal in range(1, n):
    for i in range(1, n - diagonal + 1):
      j = i + diagonal
      M[i][j], P[i][j] = minimum(M, d, i, j)

  return M, P

def minimum (M, d, i, j):
  minValue = INF
  minK = 0
  for k in range(i, j):
    value = M[i][k] + M[k + 1][j]
    value += d[i - 1] * d[k] * d[j]
      if (minValue > value):
        minValue = value
        minK = k

  return minValue, minK

곱셈 순서 출력

정의

def order (P, i, j):
  if (i == j):
    print('A%d'%(i), end='')

  else:
    k = P[i][j]
    print('('

    , end ='')

    order(P, i, k)
    order(P, k + 1, j)
    print(')'

    , end =    '')

예시코드

INF = 999
d = [5, 2, 3, 4, 6, 7, 8]
M, P = minmult(d)
print('M =')

for i in range(1, len(M)):
  print(M[i][1:])
print('P =')

for i in range(1, len(P)):
  print(P[i][1:])

print('minimum order: ', end ='')
order(P, 1, len(d) - 1)