목록알고리즘/연쇄행렬 최소곱셈 알고리즘 (1)

프로그래밍에 대한 고찰 및 생각

[1][연쇄행렬 최소곱셈 알고리즘] (Matrix chain multiplication)

연쇄행렬 최소곱셈 알고리즘 (Matrix chain multiplication) 연쇄행렬 최소곱셈 알고리즘이란 주어진 행렬들의 곱을 최소의 연산으로 수행하는 최소횟수를 구하는 알고리즘이다. 행렬의 곱셈에서 결합법칙은 성립하지만 어떤 형태로 결합되느냐에 따라 계산 횟수는 달라질수 있다. 예를 들어 아래와같은 행렬이 있다고 할때 결합 형태에 따른 연산횟수 차이는 다음과 같다. 위와 같이 결합되는 순서에 따라 전체 연산횟수가 달라짐을 알수 있다. 그렇다면 본격적으로 연쇄행렬 최소곱셈 알고리즘에 대해 알아보자. 먼저 행렬의 개수가 5개일때 모든 결합의 마지막 결합 형태는 크게 다음과같이 네가지로 분류가 가능하다. ( 행렬의 개수가 n개일때 (n-1)가지로 분류가 가능하다.) 예를 들어 (AB)(C(DE)) 는 ..
알고리즘/연쇄행렬 최소곱셈 알고리즘 2020. 3. 3. 16:03
이전 Prev 1 Next 다음