매트릭스 체인 곱하기

매트릭스 체인 곱하기(또는 매트릭스 체인 순서 문제^{[citation needed]})는 주어진 행렬의 순서를 곱하는 가장 효율적인 방법에 관한 최적화 문제다.문제는 실제로 승수를 수행하는 것이 아니라 단지 관련된 매트릭스 승수의 순서를 결정하는 것이다.그 문제는 동적 프로그래밍을 통해 해결될 수 있다.

매트릭스 곱셈은 연관성이 있기 때문에 많은 옵션이 있다.즉, 제품을 어떻게 괄호화해도 얻은 결과는 그대로 유지된다는 것이다.예를 들어, 4개의 행렬 A, B, C, D의 경우, 다섯 가지 가능한 옵션이 있다.

(AB)C)D = (A(BC))D = (AB)(CD) = A(BC)D = A(B)

제품에는 영향을 미치지 않지만 용어가 괄호화되는 순서는 제품 계산에 필요한 단순 산술 연산 수, 즉 계산 복잡성에 영향을 미친다.예를 들어 A가 10 × 30 행렬이고, B가 30 × 5 행렬이고, C가 5 × 60 행렬이라면,

컴퓨팅(AB)C 요구량(10×30×5) + (10×5×60) = 1500 + 3000 = 4500 연산

계산 A(BC) 필요 (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 연산

분명히 첫 번째 방법이 더 효율적이다.이 정보로 문제성명은 "n 행렬의 제품의 최적 괄호화를 결정하는 방법"으로 정제할 수 있다.가능한 각 괄호화(brute power)를 점검하려면 행렬의 수가 기하급수적인 런타임이 필요하며, 이는 큰 n에 대해 매우 느리고 비실용적이다.이 문제에 대한 더 빠른 해결은 문제를 일련의 관련 하위 문제로 분해함으로써 달성될 수 있다.

동적 프로그래밍 알고리즘

우선, 우리가 정말로 알고 싶은 것은 행렬을 곱하는 데 필요한 최소 비용 또는 최소 산술 연산의 수라고 가정해 보자.만약 우리가 두 행렬만을 곱하고 있다면, 그것들을 곱할 수 있는 방법은 오직 하나뿐이므로, 최소 비용은 이것을 하는 비용이다.일반적으로 우리는 다음과 같은 재귀 알고리즘을 사용하여 최소 비용을 찾을 수 있다.

• 행렬의 순서를 취하여 두 개의 반복으로 구분한다.
• 각 부속품을 곱하기 위한 최소 비용을 찾아라.
• 이 비용을 합산하고, 두 결과 매트릭스에 곱하기 위한 비용을 추가한다.
• 행렬의 순서를 분할할 수 있는 각 위치에 대해 이 작업을 수행하고 모든 행렬에 대해 최소값을 취하십시오.

예를 들어 매트릭스 ABCD가 4개인 경우 (A)(BCD), (AB)(CD), (ABC)(D) 각각을 찾는 데 필요한 비용을 계산하여 ABC, AB, CD, BCD를 계산하기 위한 최소 비용을 재귀적으로 호출한다.그런 다음 우리는 가장 좋은 것을 선택한다.더 좋은 점은, 이것은 최소 비용을 산출할 뿐만 아니라, 곱셈을 하는 최선의 방법, 즉 총 비용을 가장 적게 산출하는 방법으로 분류하고, 각 요인에 대해서도 동일한 방법으로 하는 것을 보여준다.

그러나 이 알고리즘은 기하급수적인 런타임 복잡성을 가지고 있어 모든 순열을 시도하는 순진한 접근방식만큼 비효율적이다.알고리즘이 중복 작업을 많이 하기 때문이다.예를 들어, 위에서 우리는 ABC와 AB를 모두 계산하는데 가장 좋은 비용을 찾기 위해 재귀적인 전화를 했다.그러나 ABC를 계산하기 위한 최선의 비용을 찾는 것은 또한 AB를 위한 최선의 비용을 찾는 것을 필요로 한다.재귀가 깊어질수록 이런 유형의 불필요한 반복이 점점 더 많이 일어난다.

한 가지 간단한 해결책은 메모화라고 불리운다: 우리가 특정한 부분적인 부분을 곱하는 데 필요한 최소 비용을 계산할 때마다, 우리는 그것을 절약한다.만약 우리가 그것을 다시 계산하도록 요청 받는다면, 우리는 단지 저장된 답을 줄 뿐이고, 그것을 다시 계산하지 않는다.n²/2 정도의 서로 다른 반복이 있기 때문에, 여기서 n은 행렬의 수입니다.이 간단한 트릭으로 O(2)에서ⁿ O(n³)까지 런타임이 내려간다는 것을 알 수 있는데, 이는 실제 애플리케이션에 충분히 효율적이다.이것은 하향식 동적 프로그래밍이다.

다음의 상향식 접근법은 각 2 ≤ k ≤ n에 대해 이미 계산한 더 작은 부분들의 비용을 사용하여 모든 길이 k의 부분들에 대한 최소 비용을 계산한다.그것은 동일한 무증상 런타임을 가지고 있고 재귀가 필요하지 않다.

유사 코드:

// 행렬 A[i]의 치수 보조개[i-1] x 보조개[i]는 i = 1이다.n 매트릭스체인오더(인트로 어둑어둑해지다[]) {     // 길이[길이] = n + 1     n = 어둑어둑해지다.길이 - 1;     // m[i,j] = 최소 스칼라 승수(즉, 비용)     // 행렬 A[i]를 계산해야 함A[i+1]...A[j] = A[i..j]     // 하나의 행렬을 곱할 때 비용은 0이다.     을 위해 (i = 1; i <= n; i++)         m[i, i] = 0;      을 위해 (렌 = 2; 렌 <= n; 렌++) { // 부분 길이         을 위해 (i = 1; i <= n - 렌 + 1; i++) {             j = i + 렌 - 1;             m[i, j] = 맥신트;             을 위해 (k = i; k <= j - 1; k++) {                 비용이 들다 = m[i, k] + m[k+1, j] + 어둑어둑해지다[i-1]*어둑어둑해지다[k]*어둑어둑해지다[j];                 만일 (비용이 들다 < m[i, j]) {                     m[i, j] = 비용이 들다;                     s[i, j] = k; // 최소 비용을 달성한 부분 분할 지수                 }             }         }     } } 

• 주 : 딤의 첫 번째 지수는 0이고 m과 s의 첫 번째 지수는 1이다.

해결된 운영 순서를 인쇄하기 위한 편리한 방법과 함께 제로 기반 어레이 인덱스를 사용한 Java 구현:

공중의 계급 MatrixOrderOptimization(매트릭스 순서 최적화) {     보호받는 인트로[][]m;     보호받는 인트로[][]s;     공중의 공허하게 하다 매트릭스체인오더(인트로[] 어둑어둑해지다) {         인트로 n = 어둑어둑해지다.길이 - 1;         m = 새로운 인트로[n][n];         s = 새로운 인트로[n][n];          을 위해 (인트로 lenMinusOne = 1; lenMinusOne < n; lenMinusOne++) {             을 위해 (인트로 i = 0; i < n - lenMinusOne; i++) {                 인트로 j = i + lenMinusOne;                 m[i][j] = 정수.MAX_VALUE;                 을 위해 (인트로 k = i; k < j; k++) {                     인트로 비용이 들다 = m[i][k] + m[k+1][j] + 어둑어둑해지다[i]*어둑어둑해지다[k+1]*어둑어둑해지다[j+1];                     만일 (비용이 들다 < m[i][j]) {                         m[i][j] = 비용이 들다;                         s[i][j] = k;                     }                 }             }         }     }      공중의 공허하게 하다 printOptimalParenthesization() {         부울[] 비ARESult = 새로운 부울[s.길이];         printOptimalParenthesization(s, 0, s.길이 - 1, 비ARESult);     }      공허하게 하다 printOptimalParenthesization(인트로[][]s, 인트로 i, 인트로 j,  /* 예쁜 프린팅의 경우: */ 부울[] 비ARESult) {         만일 (i != j) {             printOptimalParenthesization(s, i, s[i][j], 비ARESult);             printOptimalParenthesization(s, s[i][j] + 1, j, 비ARESult);             끈 이스트르 = 비ARESult[i] ? "_message " : " ";             끈 지르스트 = 비ARESult[j] ? "_message " : " ";             시스템.밖으로.인쇄하다("A_" + i + 이스트르 + "* A_" + j + 지르스트);             비ARESult[i] = 진실의;             비ARESult[j] = 진실의;         }     } } 

이 프로그램을 끝마칠 때, 우리는 전체 순서에 대한 최소 비용을 가지고 있다.

보다 효율적인 알고리즘

O(n³) 동적 프로그래밍 알고리즘보다 더 복잡하지만 효율적인 알고리즘이 있다.

후앤싱(1981)

Hu와 Shing에 의해 1981년에 발표된 알고리즘은 O(n log n) 연산 복잡성을 달성한다.^[2][3][4]그들은 어떻게 매트릭스 체인 곱셈 문제가 정규 다각형의 삼각 측량 문제로 변형될 수 있는지(또는 축소될 수 있는지) 보여주었다.폴리곤은 최종 결과를 나타내는 베이스라고 불리는 수평 하단이 있을 정도로 방향이 잡힌다.폴리곤의 다른 n면은 시계 방향으로 행렬을 나타낸다.한 변의 각 끝에 있는 정점은 그 변으로 표현되는 행렬의 치수들이다.곱셈 체인에 n 행렬이 있으면 n-1 이진 연산 및 C_n−1 괄호 배치 방법이 있는데 여기서 C는_n−1 (n-1)번째 카탈로니아 번호다.알고리즘은 또한 n+1 면이 있는 다각형의 C 가능한_n−1 삼각형이 있다는 것을 이용한다.

이 이미지는 정규 육각형의 가능한 삼각형을 보여준다.이것들은 5개의 행렬의 제품에 대한 곱셈을 주문하기 위해 괄호를 배치할 수 있는 여러 가지 방법에 해당한다.

아래의 예를 들면, A, B, C, 최종 결과 ABC의 4면이 있다.A는 10×30 매트릭스, B는 30×5 매트릭스, C는 5×60 매트릭스, 최종 결과는 10×60 매트릭스다.이 예제의 일반 폴리곤은 4곤, 즉 제곱이다.

매트릭스 제품 AB는 10x5 매트릭스, BC는 30x60 매트릭스다.이 예에서 가능한 두 가지 삼각측량은 다음과 같다.

• 

  (AB)C의 다각형 표현

• 

  A(BC)의 다각형 표현

필요한 곱셈의 수에 있어서 단일 삼각형의 비용은 그 정점의 산물이다.폴리곤의 특정 삼각측량 총비용은 모든 삼각측량 비용의 합이다.

(AB)C: (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 배

A(BC): (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 곱하기

Hu&Shing은 O(n log n) 시간 내에 최소 비용 파티션 문제에 대한 최적의 솔루션을 찾는 알고리즘을 개발했다.

친후싱 근사 알고리즘

근사 알고리즘의 도입에서는 친후싱 근사 알고리즘이 제시된다.이 알고리즘은 최적 삼각측량의 근사치를 산출하지만, Hu-Sing이 작업에서 사용하는 기법을 더 쉽게 이해할 수 있게 해주기 때문에 설명할 가치가 있다.

폴리곤의 각 꼭지점 V에 중량 w가 연관되어 있다.Suppose we have three consecutive vertices ${\displaystyle V_{i-1},V_{i},V_{i+1}}$, and that ${\displaystyle V_{\min }}$ is the vertex with minimum weight ${\displaystyle w_{\min }}$. We look at the quadrilateral with vertices ${\displaystyle V_{min},V_{i-1},V_i,V_{i+}}$${\displaystyle 1_{}}$ ${\$시계 방향으로).우리는 두 가지 방법으로 삼각측량을 할 수 있다.

• ${\displaystyle (V_{\min },V_{i-1},V_{i})}$ and ${\displaystyle (V_{\min },V_{i+1},V_{i})}$, with cost ${\displaystyle w_{\min }w_{i-1}w_{i}+w_{\min }w_{i+1}w_{i}}$
• ${\displaystyle (V_{\min },V_{i-1},V_{i+1})}$ and ${\displaystyle (V_{i-1},V_{i},V_{i+1})}$ with cost ${\displaystyle w_{\min }w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}}$.

그러므로 만약

${\displaystyle w_{\min }w_{i-1}w_{i-1}+w_{i-1}w_{i-1}w_{i-1}{i-1}{i-1}w_{i-1}w_{i-1}w_{i-1}w_{i+1}{i+1}:{i}}}}w_{i}w_{i}}}:{i}}}}}}}}}}}}}}}}}}}}}}}}}}}w_{i}:{i}}}}}}}}}}}$

또는 동등하게

${\displaystyle {\frac {1}{w_{i}}+{\frac {1}{w_{\min }}{\frac {1}{w_{i+1}+{\frac {1}{1}{w_{i-1}}}}}}}}}{{i-1}}}}}}}}}}}}}}}}}{\frac {\frac {1}$

다각형에서$$ 꼭지점 ${\displaystyle {Vi}_{}}$ ${\$을(를) 제거하고 $측면($- 1,${\displaystyle {}_{}}$V ${\displaystyle i_{}}$+ ${\displaystyle 1_{}}$) {\$displaystyle(V_{$i-1$},V_{i+1})$을 삼각형에$$ 추가한다.위의 조건을 만족하는$$ V ${\displaystyle i_{}}$ ${\$가 없을 때까지 이 과정을 반복한다.나머지 모든 ${\displaystyle {정점}_{}}$ $V{\displaystyle {}_{}}$ n ${\$ V_{$n}에$대해 측점$({\displaystyle {Vmin}_{}}$, ${\displaystyle {Vn}_{}}$) ${\displaystyle(V_{\min }},V_{n})$을 삼각측정에 추가한다$.$이것은 우리에게 거의 최적의 삼각측량을 제공한다.

이 구간은 확장이 필요하다.추가하면 도움이 된다.(2009년 4월)

일반화

매트릭스 체인 곱하기 문제는 보다 추상적인 문제를 해결하기 위해 일반화된다: 개체의 선형 시퀀스, 해당 개체에 대한 연관 이진 연산, 주어진 두 개 개체(모든 부분 결과뿐 아니라)에 대해 해당 작업을 수행하는 비용을 계산하는 방법, 적용할 개체를 그룹화하는 최소 비용 방법을 계산한다.순서에 따른 ^[5]작전이것의 어느 정도 조작된 특별한 경우 중 하나는 문자열 목록의 끈 연결이다.예를 들어, C에서 스트래트를 사용하여 길이 m과 n의 두 줄을 연결하는 비용은 O(m + n)이며, 첫 번째 문자열의 끝을 찾는 데 O(m + n) 시간이 필요하고, 두 번째 문자열을 그 끝에 복사하는 데 O(n) 시간이 필요하기 때문이다.이 비용 함수를 이용하여 일련의 문자열을 연결시키는 가장 빠른 방법을 찾기 위해 동적 프로그래밍 알고리즘을 작성할 수 있다.그러나 문자열의 길이를 합한 값에 비례하는 시간 내에 문자열을 직접 연결할 수 있기 때문에 이러한 최적화는 오히려 무용지물이다.단일 링크 리스트에도 비슷한 문제가 존재한다.

병렬 프로세서를 사용할 수 있을 때 문제를 해결하는 것도 일반화다.이 경우 매트릭스 제품의 각 요소를 계산하는 데 드는 비용을 추가하는 대신 동시에 할 수 있기 때문에 최대한으로 가져간다.이것은 최소 비용 및 최종 최적 그룹 모두에 큰 영향을 미칠 수 있다. 모든 프로세서를 계속 사용하게 하는 보다 "균형화된" 그룹이 선호된다.훨씬 더 정교한 접근법이 있다.^[6]

참고 항목

• 연상면체
• 타마리 격자

참조