행렬 곱셈 + 동적 프로그래밍 + 반복 관계

Question

나는 내 검토 워크 시트를 검토 중이며 동적 프로그래밍을 사용하여 체인 된 행렬 곱셈에 대한 반복 관계를 찾는 데 도움을 찾고자했습니다.

문제는 관련 차원 시퀀스 (d0, d1, … ,dn) 인 체인 된 행렬 제품 M0M1…Mn - 1에 대한 최적의 괄호 안에 문제가 있다고 생각하십시오. 이 문제에 대한 동적 프로그래밍 솔루션의 기반이되는 반복 관계, 즉 체인 제품 MiM1…Mj의 모든 괄호 안에 곱셈의 최소 수 mij에 대한 반복 관계를 유도합니다. 초기 조건을 잊지 마라.

M[i,j](M[i,j] = M[i,k] + M[k+1,j] + pqr)에 대한 수식을 이해합니다. 이것은 확실히 재귀가 있습니다. 그러나 나는 어떻게 재발 관계를 결정 하는가? 이것은 재발 관계가 아닌가? 또한 "연관 차원 공간"은 무엇을 의미합니까?

Answer 1

보기 여기 관련된 측정 기준에 의해 http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

에서 6.5 (체인 매트릭스 곱셈) 그 M2 등등 .... (D2)을 가지며, M1은 (D1)을 가지며, 각각의 매트릭스 즉 M0의 치수는 치수 (D0)를 갖는 것을 의미한다.