Complex Matrices Multiply Problem 을 Divide and Conquer 로 설계하기(6 Matrices)

소개

다중 행렬 곱셈 계산 문제를 해결하기 위한 접근방법으로 Divide and Conquer 방식을 사용하여 solution 을 설계했을 때 어떤 방식으로 문제를 해결할 수 있는지와 그에 따르는 문제점들을 나열하고,
그 문제점들을 해결하기 위한 방법을 Dynamic Programming 을 사용했습니다.
또한 왜 Dynamic Programming 접근방식이 D&C 접근 방식보다 CMM 에 적합한지에 대한 간략한 이유 설명을 추가하였으며 두 접근 방식을 해결하기 위해 작성한 소스 코드와 실행 결과를 추가하였습니다.

수식보다는 예시를 통하여 설명하였습니다.

목차

없음

본문내용

주어진 문제
C 로 설계하기
Divide the given problem into small problems.
주어진 n 개의 행렬에 대해 1~k 번째 행렬까지 곱한 행렬과 그 나머지를 곱한 행렬의 곱으로 문제를 나눈다.
나뉜 행렬을 곱한 총 연산횟수를 반환하는 CMM_DnC()라는 함수가 있다고 할 때, 나뉘어 계산된 행렬 과 를 곱셈한 총 연산 횟수는 다음과 같다.
A 에서 언급한 k 의 위치를 변경해가면서 어떤 행렬을 기준으로 두 그룹으로 나누었을 때 연산결과가 가장 작을지를 반복하며 검색한다.
Conquer those steps.
자체가 Combine 의 역할을 수행하고 있으므로 특별히 Combine 단계가 존재하지 않는다.
Source code
int CMM_DnC(int dim[], int start, int end) {
int smallest = INT_MAX;

이하생략

참고자료

· 없음