이 기사에서는 Java Matrix Multiplication Problection (Dynamic Programming) 알고리즘에 대해 설명합니다. 다음과 같이 참조에 대해 공유하십시오.
문제 설명 : 주어진 N 행렬 : A1, A2, ..., an, 여기서 AI 및 AI+1은 곱하기, i = 1, 2 ..., N-1입니다. 매트릭스 연속 제품을 계산하는 계산 순서를 결정 하여이 순서로 매트릭스 연속 제품을 계산하는 데 필요한 곱셈의 수가 가장 적습니다. 입력 데이터는 각 행렬의 수와 각 행렬의 크기이며 출력 결과는 계산 순서와 행렬의 연속 제품에 대한 최소 곱셈 수입니다.
문제 분석 : 매트릭스 곱셈은 연관 법칙을 만족시키기 때문에 매트릭스의 연속 제품을 계산하기위한 여러 계산 순서가있을 수 있습니다. 이 계산 순서는 괄호를 추가하여 결정할 수 있습니다. 매트릭스 연속 생성물의 계산 순서가 완전히 결정되면, 즉 연속 제품이 완전히 괄호로 만들어지면, 두 행렬의 곱셈을위한 표준 알고리즘은이 순서에서 반복적으로 호출되어 매트릭스 연속 제품을 계산할 수 있습니다.
완전히 괄호 된 매트릭스 생성물은 재귀 적으로 다음과 같이 정의 될 수 있습니다.
(1) 단일 매트릭스는 완전히 괄호가있다.
(2) 매트릭스 생성물 A는 완전히 괄호로 묶여 있고, A는 완전히 괄호가있는 매트릭스 제품 B 및 C의 제품으로 표현 될 수 있으며, 괄호, 즉 A = (BC)
예를 들어, 매트릭스 생성물 A1A2A3A4 : (A1 (A2 (A2 (A2A4))), (A1 (A1A3) A4)), (A1A2) (A3A4)), ((A1 (A2A3)) A4)를 완전히 괄호로 만드는 5 가지 방법이 있습니다. 완전 괄호의 각 방법은 매트릭스 연결 제품의 계산 순서에 해당하며, 이는 제품을 만드는 데 필요한 계산량을 결정합니다.
다음 예를 참조하십시오. 세 행렬 곱셈 {A1, A2, A3}; 치수는 각각 10*100, 100*5, 5*50입니다. 이 순서에서 필요한 횟수를 계산하십시오 ((A1*A2)*A3) : 10x100x5+10x5x50 = 7500 회,이 순서에서 필요한 횟수를 계산하십시오 (a1*(a2*a3)) : 10*5*50+10*50 = 75000 회
따라서 문제는 다음과 같습니다. 계산 금액을 최소화 할 수 있도록 작업 순서를 결정하는 방법입니다.
알고리즘 아이디어 :
예 : 각 행렬의 치수가
A1 : 30*35; A2 : 35*15; A3 : 15*5; A4 : 5*10; A5 : 10*20; A6 : 20*25
재귀 관계 :
설계 계산 A [i : j], 1≤i≤j≤n 및 최소 곱셈 수는 m [i, j]이 필요하며 원래 문제의 최적 값은 m [1, n]입니다.
i = J, a [i : j] = ai, 따라서 m [i] [i] = 0, i = 1,2,…, n
I <J 일 때, AK와 AK+1 사이의 최적 순서가 분리되면 i <= k <j, 다음 : M [i] [J] = M [i] [k]+m [k+1] [j]+pi-1pkpj. 단절 지점의 위치 k는 계산 중에 알려지지 않기 때문에 K는 아직 결정되지 않았습니다. 그러나 k 위치에는 Ji 만 가능합니다. 따라서 K는 JI 위치가 계산량을 최소화하는 위치입니다.
요약하면 다음과 같이 재귀 관계가 있습니다.
최적의 솔루션 구성 :
상응하는 m [i] [j]의 단절 위치 k가 s [i] [j]로 표시되는 경우, 최적의 값 m [i] [j]를 계산 한 후, 상응하는 최적 솔루션은 s [i] [j]로부터 재귀 적으로 구성 될 수있다. s [i] [j]의 숫자는 행렬 체인 A [i : j]를 계산하는 가장 좋은 방법이 행렬 AK와 AK+1 사이에 분리되어야 함을 보여줍니다. 따라서 S [1] [n]에 의해 기록 된 정보에서, 우리는 [1 : n]을 계산하기위한 최적의 괄호가 (a [1 : s [1] [n]]) (a [s [1] [n] +1 : n])임을 알 수 있습니다. 추가로, [1 : s [1] [s [1] [s [1] [n]]에 대한 최적의 괄호는 (a [s [1] [1] [n]]+1 : s [1] [1] [S [1] [n]])입니다. 마찬가지로, [s [1] [n] +1 : n]의 최적 괄호가 s [s [1] [n] +1] [n]에서 깨 졌다는 것을 결정할 수 있습니다. 우리가 이것을 계속 되돌려면, 우리는 [1 : n]의 최적의 완전한 괄호를 결정하고 문제에 대한 최적의 해결책을 구성 할 수 있습니다.
패키지 행렬; 공개 클래스 매트릭스 {public static void matrixchain (int [] p, int n, int [] m, int [] s) {for (int i = 1; i <= n; i ++) {m [i] [i] = 0; } for (int r = 2; r <= n; r ++) {for (int i = 1; i <= n-r+1; i ++) {int j = i+r-1; m [i] [j] = m [i + 1] [j] + p [i-1]*p [i]*p [j]; S [i] [J] = I; for (int k = i+1; k <j; k ++) {int t = m [i] [k]+m [k+1] [j]+p [i-1]*p [k]*p [j]; if (t <m [i] [j]) {m [i] [j] = t; S [i] [J] = K; }}}}} public static void traceback (int i, int j, int [] [] s) {if (i == j) return; 트레이스 백 (i, s [i] [j], s); 트레이스 백 (s [i] [j] + 1, j, s); System.out.println ( "" + i + "," + s [i] [j] + "및" + (s [i] [j] + 1) + "," + j); } public static void main (String [] args) {System.out.println ( "wulin.com 테스트 결과 :"); Matrix MC = 새로운 행렬 (); int n = 7; int p [] = {30, 35, 15, 5, 10, 20, 25}; int m [] [] = new int [n] [n]; int s [] [] = new int [n] [n]; int l = p.length-1; Mc.matrixchain (P, L, M, S); for (int i = 1; i <n; i ++) {for (int j = 1; j <n; j ++) {system.out.print (m [i] [j]+"/t"); } system.out.println (); } system.out.println (); for (int i = 1; i <n; i ++) {for (int j = 1; j <n; j ++) {system.out.print (s [i] [j]+""); } system.out.println (); } mc.traceback (1, 6, s); }}실행 결과 :
Java 알고리즘에 대한 자세한 내용은이 사이트에 관심이있는 독자들이 주제를 볼 수 있습니다. "Java 데이터 구조 및 알고리즘 자습서", "Java Operation Dom Node Tips 요약", "Java 파일 및 디렉토리 작동 팁 요약"및 "Java Cache Operation Tips의 요약"을 볼 수 있습니다.
이 기사가 모든 사람의 Java 프로그래밍에 도움이되기를 바랍니다.