Chained Matrix Multiplication (연쇄 행렬 곱셈)
: 행렬 i x j와 행렬 j x k 처럼 열의 갯수와 행의 갯수가 같은 연속적인 행렬의 곱셈
- 행렬의 곱은 결합법칙이 적용하기 때문에 곱하는 순서는 상관없지만 곱하는 횟수가 달라지기 때문에 최적의 순서를 구해야한다.
e.g.
A1 x A2 x A3.
A1은 10 x 100, A2는 100 x 5, A3은 5 x 50.
(A1 x A2) x A3
10 x 100 x 5 + 10 x 5 x 50 = 7,500
A1 x (A2 x A3)
100 x 5 x 50 + 10 x 100 x 50 = 75,000 //100을 2번 계산하기 때문에 연산 횟수가 증가함
Brute force algorithm
: 전부 해보기
이런 방법에 대한 시간복잡도를 알아야할까
아무튼 Θ(2^n)인걸루.
Dynamic Programming Design
A1부터 An까지 연속된 행렬의 곱을 계산한다면
각 행과 열의 값을 살펴봤을 때 A1의 행의 값을 d0, A1의 열의 값을 d1이라고 한다면 행렬 A는 곱이 가능한 연속된 행렬이기 때문에 A2의 값이 d1과 동일하다.
그렇기 때문에 행렬들의 곱은 d0 x d1 x ... x dn이라고 할 수 있다.
만약 1 <= i <= j <= n인 i와 j가 있다면 M[i][j]의 최소값은
M[i][k] + M[k+1][j] + d[i-1]d[k]d[j]의 최소값으로 계산할 수 있다.
(A(B(CD)), ((AB)(CD)), A((BC)D) 처럼 곱 계산의 위치를 변수 k로 설정하여 최소값을 찾을 수 있다.
M[i][k]는 Ai에서 Ak까지 행렬 곱 연산 횟수,
M[k-1][j]는 Ak-1엣 Aj까지 행렬 곱 연산 횟수,
d[i-1]*d[k]*d[j]는 dp[i][k]와 dp[k+1][j]의 행렬 곱 연산 횟수이다.
Example
M[4][6]을 계산할 때 ((A4xA5)xA6)과 (A4x(A5xA6)) 중에 더 작은 값을 찾는 경우에 둘 다 계산하여 더 작은 값을 사용한다.
아무튼 diagonal을 n-1번 계산해서 값을 찾아낸다.?
각 단계에서의 계산은 n-diag개가 필요하다.
ex. diag1의 경우는 6-1(n-diag)개가 필요하다.
∴ 전체적으로 1<=diag<= n-1 번 연산하고 각 diag는 n-diag번 계산한다.
//저 선들이 뭘 의미하는지 아시는 분 계시면 알려주세요ㅠ
Minimum Multiplication
- Problem : n개의 행렬을 곱하는데 필요한 최소 곱셈 수와 그 최소 수를 산출하는 순서를 결정한다.
- Input : 행렬의 크기 n, 0부터 n까지 정렬된 배열 dk < di-1 x di는 i번째 행렬이다.
- output : n개의 행렬 곱을 위해 필요한 최소 곱셈 수, 최적의 차수를 얻을 수 있는 2차원 배열 P, < P[i][j]는 최적의 순서로 행렬을 나누는 point
//Minimum Multiplication Algorithm
int minmuit(int n, const int d[], index P[][]) {
index i, j, k, diagonal;
int M[1..n, l..n]; //n의 크기로 배열 M 생성
for(i = 1; i <= n; i++)
M[i][j] = 0; //자기 자신으로부터의 거리는 0
for(diagonal = 1; diagonal <= n-1; diagonal++) //diagonal 배열 만들기?
for(i = 1; i <= n-diagonal; i++) {
j = i + diagonal; //현재로서 가장 큰 값
M[i][j] = minimum(M[i][k] + M[k+1][j]+d[i-1]*d[k]*d[j]);
//i <= k <= j - 1
P[i][j] = 최소값을 제공하는 k의 값;
}
return M[1][n]; //최종적으로 계산된 결과 값
}
그럼 뭐 이런식으로 된다고 생각하면 된다는거죠?
Every Case Time Complexity : Minimum Multiplication
- Basic operation : n의 값에 의해 실행되는 명령어? 최소 값을 위한 비교 테스트..- Input size : 곱할 행렬의 수 n- Analysis
아마 전체적으로 1<=diag<= n-1 번 연산하고
각 diag는 n-diag번 계산하기 때문에 전체적으로 반복하는거 아닐까?
몰라요 교수님이 안알려줌
'아무튼 공부중 > algorithm' 카테고리의 다른 글
[알고리즘] Monte Carlo Algorithm | Sum of Subsets Problem | Hamiltonian Circuits Problem (1) | 2023.12.06 |
---|---|
[알고리즘] Backtracking | n Queens Problem (0) | 2023.12.03 |
[알고리즘]Graph Theory | 그래프 이론 (1) | 2023.10.22 |
[알고리즘]The Binamial Conefficient with Pascal's Triangle | 파스칼의 삼각형을 이용한 이항계수 알고리즘 (1) | 2023.10.21 |
[알고리즘]Matrix Multiplication with Strassen's Algorithm (1) | 2023.10.21 |