dynamic-programming
행렬 곱셈

재귀 적 솔루션

행렬 곱셈 은 동적 프로그래밍을 사용하여 해결할 수있는 최적화 문제입니다. 일련의 행렬이 주어지면 목표는 이들 행렬을 곱하는 가장 효율적인 방법을 찾는 것입니다. 문제는 실제로 곱셈을 수행하는 것이 아니라 행렬 곱셈의 순서를 결정하는 것입니다.

우리가 차원 m * n 과 p * q의 두 개의 행렬 A ₁ 과 A ₂ 를 가지고 있다고 가정 해 봅시다. 행렬 곱셈의 규칙으로부터 우리는,

1. n = p 인 경우에만 A ₁ 과 A _2를 곱할 수 있습니다. 즉, A ₁ 의 열 수는 A ₂ 의 행 수와 같아야합니다.
2. 첫 번째 조건을 만족하고 우리가 번성 _{1과 2를한다면,} 우리는 새로운 행렬을 얻을의는 ₃ 차원의 m의 * q를 호출 할 수 있습니다.
3. A ₁ 과 A ₂ 를 곱하기 위해서, 우리는 몇몇 스케일러 곱셈을 할 필요가 있습니다. 우리가 수행해야하는 총 스케일러 곱셈의 수는 ( m * n * q ) 또는 ( m * p * q )입니다.
4. A ₁ * A ₂ 는 A ₂ * A ₁ 과 같지 않습니다.

차원 m * n , n * p 및 p * q를 각각 갖는 ₃ 개의 행렬 A ₁ , A ₂ 및 A ₃ 가있는 경우 A ₄ = A ₁ * A ₂ * A _3의 차원은 m * q가 됩니다. 이제이 행렬 곱셈을 두 가지 방법으로 수행 할 수 있습니다.

• 먼저 A ₁ 과 A ₂ 를 곱한 다음 A ₃ 을 곱합니다. 즉 : ( A ₁ * A ₂ ) * A ₃ .
• 먼저 A ₂ 와 A ₃ 을 곱한 다음 결과에 A ₁ 을 곱합니다. 즉, A ₁ * ( A ₂ * A ₃ )입니다.

곱셈의 순서가 동일하게 유지됨을 알 수 있습니다. 즉, 유효하지 않을 수 있으므로 곱하기 ( A ₁ * A ₃ ) * A _2를 곱하지 않습니다. 나머지와 곱하기 전에 괄호 를 변경하여 집합을 곱합니다. 이 괄호를 어떻게 배치 할 것인가가 중요합니다. 왜? 예를 들어, 3 개의 행렬 A ₁ , A ₂ 및 A ₃ 의 차원은 10 * 100 , 100 * 5 , 5 * 50 입니다. 그때,

1. ( A ₁ * A ₂ ) * A _{3의 경우} , 스케일러 곱셈의 총 수는 ( 10 * 100 * 5 ) + ( 10 * 5 * 50 ) = 7500 입니다.
2. A ₁ * ( A ₂ * A ₃ )의 경우, 스케일러 곱셈의 총 수는 ( 100 * 5 * 50 ) + ( 10 * 100 * 50 ) = 75000 입니다.

두 번째 유형의 경우 스케일러 곱셈의 수는 첫 번째 유형의 수의 10 배입니다! 따라서 전체 스케일러 곱셈을 최소화하는 데 필요한 괄호 올바른 방향을 찾는 방법을 고안 할 수 있다면 행렬 곱셈에 필요한 시간과 메모리가 모두 줄어 듭니다. 이것은 행렬 체인 곱셈이 도움이되는 곳입니다. 여기에서는 행렬의 실제 곱셈에 대해서는 고려하지 않을 것이며 올바른 괄호 순서 만 찾아야 스케일러 곱셈의 수가 최소화됩니다. 우리는 행렬 A ₁ , A ₂ , A ₃ ....... A _n을 가질 것이고, 우리는 이것을 곱하는 데 필요한 최소 스케일러 곱셈의 수를 알아낼 것입니다. 주어진 차원이 유효하다고 가정합니다. 즉, 행렬 곱셈에 대한 첫 번째 요구 사항을 만족합니다.

우리는 divide-and-conquer 방법을 사용하여이 문제를 해결할 것입니다. 일반적인 하위 문제로 인해 동적 프로그래밍이 필요합니다. 예를 들어, n = 5 인 경우 5 개의 행렬 A ₁ , A ₂ , A ₃ , A ₄ 및 A _5가 있습니다. 이 행렬 곱셈을 수행하는 데 필요한 곱셈의 최소 수를 알아 내야합니다. A ₁ * A ₂ * A ₃ * A ₄ * A ₅ . 여러 가지 방법 중 하나에 집중 해 봅시다. ( A ₁ * A ₂ ) * ( A ₃ * A ₄ * A ₅ ).

이 일을 위해, 우리는 _왼쪽 = A ₍₁₎ *로 _2를 찾을 수 있습니다. _우측 = ₃ * ₄ * _5. 그런 다음 우리는 _답 = A _왼쪽 * _권리를 찾을 수 있습니다. _답을 찾을 필요 스케일러 곱셈의 총 수는 : *는 _왼쪽 + _오른쪽 + A _왼쪽을 결정하는 데 필요한 스케일러 곱셈의 총 수를 결정하는 데 필요한 스케일러 곱셈의 총 수를 결정하는 데 필요한 스케일러 곱셈의 총 수 = _권리 .

행 수 _레프트 *의 열 수 _레프트 * _{오른쪽에있는} 열 수 : 마지막 항은 _왼쪽 * _권리를 결정하는 데 필요한 스케일러 곱셈의 총 수는 같이 쓸 수있다. (행렬 곱셈의 제 2 규칙에 따라)

그러나 다른 방법으로도 괄호를 설정할 수 있습니다. 예 :

• A ₁ * ( A ₂ * A ₃ * A ₄ * A ₅ )
• ( A ₁ * A ₂ * A ₃ ) * ( A ₄ * A ₅ )
• ( A ₁ * A ₂ * A ₃ * A ₄ ) * A ₅ 등

각각의 가능한 모든 경우에, 우리는 그 다음 _왼쪽 * _오른쪽에 대한 _{왼쪽과 오른쪽을} 발견 할 필요가 스케일러 곱셈의 수를 결정합니다. 재귀에 대한 일반적인 생각이 있다면이 작업을 수행하는 방법을 이미 이해했을 것입니다. 우리의 알고리즘은 다음과 같습니다.

- Set parenthesis in all possible ways.
- Recursively solve for the smaller parts.
- Find out the total number of scaler multiplication by merging left and right.
- Of all possible ways, choose the best one.

왜 이것이 동적 프로그래밍 문제입니까? ( A ₁ * A ₂ * A ₃ )을 결정하기 위해 이미 ( A ₁ * A ₂ )를 계산했다면이 경우에 도움이 될 것입니다.

이 재귀의 상태를 결정하기 위해 각각의 경우를 해결하기 위해 우리가 작업하고있는 행렬의 범위를 알아야합니다. 그래서 우리는 시작 과 끝 이 필요할 것입니다. 우리가 나누기와 정복을 사용함에 따라, 우리의 기본 경우에는 곱하기 필요가없는 행렬이 2 개 미만 ( begin > = end )이됩니다. 행 과 열의 두 배열을 갖게 됩니다 . row [i] 와 column [i] 는 행렬 A _i에 대한 행과 열의 수를 저장합니다. 우리는 이미 계산 된 값을 저장하고 -1 아직 계산되지 않은 값을 나타내고 -1로 초기화하는 DP [N] [N] 배열을 가질 것이다. dp [i] [j] 는 A _i , A _{i + 1} , ....., A _j 를 곱하는 데 필요한 스칼라 곱셈의 수를 나타냅니다. 의사 코드는 다음과 같습니다.

Procedure matrixChain(begin, end):
if begin >= end
    Return 0
else if dp[begin][end] is not equal to -1
    Return dp[begin][end]
end if
answer := infinity
for mid from begin to end
    operation_for_left := matrixChain(begin, mid)
    operation_for_right := matrixChain(mid+1, right)
    operation_for_left_and_right := row[begin] * column[mid] * column[end]
    total := operation_for_left + operation_for_right + operation_for_left_and_right
    answer := min(total, answer)
end for
dp[begin][end] := answer
Return dp[begin][end]

복잡성:

begin 과 end 의 값은 1 에서 n까지 입니다. n ^개의 다른 상태가 있습니다. 각 상태에 대해 내부 루프는 n 번 실행됩니다. 총 시간 복잡성 : O(n³) 및 메모리 복잡성 : O(n²) .