04_week_행렬체인곱셈

행렬을 묶는 순서에따라 곱셈을 하는 수가 달라진다.
곱셈의 수가 늘어나면 시간적으로 손해를 보게되니 곱셈의 수를 최소화하는 방법을 찾아야한다

괄호 묶는 방법의 수

동적 프로그래밍의 적용
1. 최적해의 구조의 특징을 찾기
2. 최적해의 갑을 재귀적으로 정의
3. 최적해의 값을 계산
4. 계산된 정보들로부터 최적해를 구성

점화식 설명 -- 2단계와 관련
재귀해
m[i][j]를 행렬 $A_{i...j}$ 를 계산하는데 필요한 최소한의 스칼라 곱의 수라고 가정
(전체 문제에 대해서는 $A_{1..n}$을 계산하는 가장 비용이 적게 드는 방법의 비용은 m[1,n]이 될 것임)

1. i==j
   행력 곱셈 문제는 하나의 행렬로 구성되므로 결과를 계산하는데 스칼라 곱이 필요하지 않음(행과 열이 같은 하나의 행렬로 구성되었다는 말)
   따라서 i=1,2,...,n 에 대해 m[i][i]=0 임

2. i<j
   m[i][j]를 계산하기 위해서 첫 번째 단계에서의 최적해 구조의 이점을 활용
   $A_i$ $A_{i+1}$ ••• $A_j$ 를 최적으로 괄호로 묶기 위해서는 $A_k$와 $A_k+1$ (i<=k<j)사이에서 나눈다고 가정
   $m[i][j]$는 부분 결과 $A_{i...k}$ 와 $A_{k+1...j}$를 게산하는데 필요한 최소 비용과 두개의 행렬을 곱하는데 필요한 비용의 합
   각 행렬 $A_i$ 가 $P_{i-1}*P_i$ 이므로

$A_{i...k}A_{k+1...j}$ 구하기 위해서는 $P_{i-1} x P_k x P_j$ 임

이를 점화식으로 표현하면
$m[i][j]=m[i][k]+m[k+1][j]+P_{i-1} x P_k x P_j$

이중 최소를 구하는 방법은

정리

sudo code

n=len(p)-1
m=[][] # ex table
s=[][] # ex table 2
for i in range (1,n):
	m[i][i]=0
for l in range (2,n): # l은 chain 의 길이
	for i in range(1, n-l+1):
    	j=i+l-1
        m[i][j]=INF # INF = infinite
        for k in range(i,j-1):
        q=m[i][k]+m[k+1][j]+P[i][0]*P[k][1]*P[j][1]
        if q<m[i][j]:
        	m[i][j]=q
            s[i][j]=k # 최적 괄호 묶기의 자르는 k 값을 저장하는 공간
return m, s