연쇄행렬 최소곱셈 알고리즘

이 알고리즘의 주요 사용

- 행렬 곱셈의 연산의 경우의 수 중 최솟값를 구할 때

- 꼭 행렬 문제가 아니더라도 각각의 합의 최소비용

​

행렬은 결합법칙이 존재하는데, 각각 연산횟수가 같으면 좋겠지만, 불행히도 다르다.

ABC = (AB)C

ABC = A(BC)

​

연쇄행렬 최소곱셈 알고리즘은 아래 법칙을 통해 행렬곱셈의 횟수를 최소로 구할 수 있다.

-DP[i][j] = minimum(DP[i][k]+DP[k+1][j]+d[i-1]*d[k]*d[j])

​

ex)

A(20x1), B(1x30), C(30x10), D(10x10) 일때,

d0=20, d1=1, d2=30, d3=10, d4=10

​

1.행렬 A~B까지의 곱의 횟수 :

DP[1][2] = minimum(DP[1][k] + DP[k+1][2] + d0*dk*d2)

​

2.행렬 B~C까지의 곱의 횟수 :

DP[2][3] = minimum(DP[2][k] + DP[k+1][3] + d1*dk*d3)

​

3.행렬 A~C까지의 곱의 횟수 :

DP[1][3] = minimum(DP[1][k]+DP[k+1][3]) + d0*dk*d3)

= minimum(DP[1][1] + DP[2][3] + d0*d1*d3, DP[1][2], DP[3][3] + d0*d2*d3)

직접 계산해보시면 알겠지만, 결국엔 빨간색 부분의 로직을 계산하는게 목표이고, 그 값을 DP에 저장해서 최솟값을 얻어낸다.

​

이런식으로 DP[4][4]까지 계산해 간다면

​

1. DP[1][1], DP[2][2], DP[3][3], DP[4][4]

​	1	2	3	4
1	0
2		0
3			0
4				0

2.dp[4][4]의 값은 아래 표처럼 추출할 수 있다.

​	1	2	3	4
1	0	600	500	600
2		0	300	400
3			0	3000
4				0

설명은 꼭 필요한것만 작성했으니 꼭 관련문제를 풀어봐야 한다.

문제를 풀지않는다면, 당신은 공부하지 않은것과도 같다.

아래링크는 관련문제의 예제이다.

​

파일합치기 : https://won-percent.tistory.com/22

행렬 곱셈 순서 : https://blog.naver.com/hands731/221809328197

출처 : https://blog.naver.com/hands731/221809214829