연쇄 행렬 곱샘 알고리즘

MinMatMut(n, d[]) {

  int i, j, k, s;

  int C[n+1][n+1] ; 

  for(i=1; i<=n; i++) C[i][i] = 0;

  for(s=1; s <= n-1; s++) {

    for(i=1; i <= n-s; i++) {

      j = i + s;

      C[i][j] = min/mini≤k≤j-1/ (C[i][k]+C[k+1][j]+d[i-1]d[k]d[j]); 

      P[i][j] = 최소값이 되는 k의 값;

    }

  return C[1][n];

}

*연쇄 행렬 곱셈 문제의 점화식*

M1 × M2 × M3 × …  × Mn-1 × Mn   --->  (d0×d1)* (d1×d2)*( d2×d3)*......*( dn-2×dn-1)*( dn-1×dn)

C(i,j) || 1≤i≤j≤n

-->  Mi×Mi+1×Mi+2×…×Mj-1×Mj를 수행하는 데 필요한 곱셈의 최소 횟수 

C(i, i) = 0, 1≤i≤n

C(i, i+1) = di-1didi+1 

C(i, i+2) = min{ Mi(Mi+1Mi+2) + 결합비용,  
              (MiMi+1)Mi+2 + 결합비용 } 

          = min{ C(i, i)+C(i+1, i+2) + di-1didi+2 , 
             C(i, i+1)+C(i+2, i+2) + di-1di+1di+2 } 

C(i, i+3) = min{  Mi(Mi+1Mi+2Mi+3) + 결합비용,

               (MiMi+1)(Mi+2Mi+3) + 결합비용,

                (MiMi+1Mi+2)Mi+3 + 결합비용 }

              = min{ C(i, i)+C(i+1, i+3) + di-1didi+3 ,  

                 C(i, i+1)+C(i+2, i+3) + di-1di+1di+3 ,

                 C(i, i+2)+C(i+3, i+3) + di-1di+2di+3 

일반화된 점화식

 

C(i, j) = mini≤k≤j-1 { (Mi…Mk)(Mk+1…Mj) + 결합비용 } = mini≤k≤j-1 { C(i, k) + C(k+1, j) + di-1dkdj }