Java의 메모화(1D, 2D 및 3D) 동적 프로그래밍-java지도 시간-php.cn

메모이제이션은 제공된 입력에 대한 결과(배열에 저장됨)를 기록하여 동일한 입력 집합에서 메소드가 여러 번 실행되지 않도록 하여 재귀 알고리즘의 성능을 향상시키는 데 사용되는 동적 프로그래밍 기반 기술입니다. 메모화는 재귀적 방법을 구현하는 하향식 접근 방식을 통해 달성할 수 있습니다.

기본 피보나치 수열 예제를 통해 이 상황을 이해해 보겠습니다.

1-D 메모이제이션

우리는 상수가 아닌 매개변수가 하나만 있는(하나의 매개변수 값만 변경됨) 재귀 알고리즘을 고려할 것이므로 이 방법을 1-D 메모라고 합니다. 다음 코드는 피보나치 수열에서 N번째(N까지의 모든 항)를 찾는 코드입니다.

Example

public int fibonacci(int n) {
   if (n == 0)
      return 0;
   if (n == 1)
      return 1;
   System.out.println("Calculating fibonacci number for: " + n);
   return (fibonacci(n - 1) + fibonacci(n - 2));
}

로그인 후 복사

Output

위 코드를 n=5로 실행하면 다음과 같은 출력이 생성됩니다.

Calculating fibonacci number for: 5
Calculating fibonacci number for: 4
Calculating fibonacci number for: 3
Calculating fibonacci number for: 2
Calculating fibonacci number for: 2
Calculating fibonacci number for: 3
Calculating fibonacci number for: 2

로그인 후 복사

n=5에 대한 피보나치 값은 다음과 같습니다. 5

2와 3에 대한 피보나치 수는 여러 번 계산됩니다. n=5 조건에 대해 위의 재귀 트리를 그려서 더 잘 이해해 보겠습니다.

노드의 두 자식은 재귀 호출을 나타냅니다. F(3)과 F(2)가 여러 번 계산되는 것을 볼 수 있는데, 이는 각 단계 후에 결과를 캐싱하여 방지할 수 있습니다.

우리는 결과를 캐시하기 위해 인스턴스 변수 memoize Set을 사용할 것입니다. 먼저 메모화 세트에 n이 이미 존재하는지 확인하고, 존재하지 않으면 값을 반환하고, 값을 계산하여 세트에 추가합니다.

Example

import java.util.HashMap;
import java.util.Map;
public class TutorialPoint {
   private Map<Integer, Integer> memoizeSet = new HashMap<>(); // O(1)
   public int fibMemoize(int input) {
      if (input == 0)
         return 0;
      if (input == 1)
         return 1;
      if (this.memoizeSet.containsKey(input)) {
         System.out.println("Getting value from computed result for " + input);
         return this.memoizeSet.get(input);
      }
      int result = fibMemoize(input - 1) + fibMemoize(input - 2);
      System.out.println("Putting result in cache for " + input);
      this.memoizeSet.put(input, result);
      return result;
   }
   public int fibonacci(int n) {
      if (n == 0)
         return 0;
      if (n == 1)
         return 1;
      System.out.println("Calculating fibonacci number for: " + n);
      return (fibonacci(n - 1) + fibonacci(n - 2));
   }
   public static void main(String[] args) {
      TutorialPoint tutorialPoint = new TutorialPoint();
      System.out.println("Fibonacci value for n=5: " + tutorialPoint.fibMemoize(5));
   }
}

로그인 후 복사

Output

위 코드를 실행하면 다음과 같은 출력이 생성됩니다

Adding result in memoizeSet for 2
Adding result in memoizeSet for 3
Getting value from computed result for 2
Adding result in memoizeSet for 4
Getting value from computed result for 3
Adding result in memoizeSet for 5

로그인 후 복사

n=5에 대한 피보나치 값은 5

위에서 볼 수 있듯이 에 대한 피보나치 값은 2 및 3 증서 번호는 다시 계산되지 않습니다. 여기서는 계산된 값을 저장하는 HashMap을 소개합니다. 각 피보나치 계산 전에 입력 값이 컬렉션에 계산되었는지 확인합니다. 그렇지 않은 경우 컬렉션에 특정 입력 값을 추가합니다.

2-D 암기

위 프로그램에는 상수가 아닌 매개변수가 하나만 있습니다. 다음 프로그램에서는 각 재귀 호출 후에 값을 변경하는 두 개의 매개변수가 있는 재귀 프로그램의 예를 들고 최적화를 위해 상수가 아닌 두 매개변수에 대한 메모이제이션을 구현합니다. 이를 2D 메모라고 합니다.

예: 표준 Longest Common Subsequence (LCS)을 구현합니다. 시퀀스 집합이 주어지면 가장 긴 공통 부분 수열 문제는 가장 큰 길이를 갖는 모든 시퀀스에 공통되는 부분 수열을 찾는 것입니다. 가능한 조합은 2^n개입니다.

Example

class TP {
   static int computeMax(int a, int b) {
      return (a > b) ? a : b;
   }
   static int longestComSs(String X, String Y, int m, int n) {
      if (m == 0 || n == 0)
         return 0;
      if (X.charAt(m - 1) == Y.charAt(n - 1))
         return 1 + longestComSs(X, Y, m - 1, n - 1);
      else
         return computeMax(longestComSs(X, Y, m, n - 1), longestComSs(X, Y, m - 1, n));
   }
   public static void main(String[] args) {
      String word_1 = "AGGTAB";
      String word_2 = "GXTXAYB";
      System.out.print("Length of LCS is " + longestComSs(word_1, word_2, word_1.length(),word_2.length()));
   }
}

로그인 후 복사

Output

위 코드를 실행하면 다음과 같은 출력이 생성됩니다

Length of LCS is 4

로그인 후 복사

Java의 메모화(1D, 2D 및 3D) 동적 프로그래밍

위 재귀 트리에서 lcs("AXY", "AYZ")는 여러 번 풀립니다.

하위 구조가 겹치는 문제의 특성상 메모나 표 작성을 사용하면 동일한 하위 문제에 대한 반복 계산을 피할 수 있습니다.

재귀코드의 메모화 방식은 다음과 같이 구현됩니다.

Example

import java.io.*;
import java.lang.*;
class testClass {
   final static int maxSize = 1000;
   public static int arr[][] = new int[maxSize][maxSize];
   public static int calculatelcs(String str_1, String str_2, int m, int n) {
      if (m == 0 || n == 0)
         return 0;
      if (arr[m - 1][n - 1] != -1)
         return arr[m - 1][n - 1];
      if (str_1.charAt(m - 1) == str_2.charAt(n - 1)) {
         arr[m - 1][n - 1] = 1 + calculatelcs(str_1, str_2, m - 1, n - 1);
         return arr[m - 1][n - 1];
      }
      else {
         int a = calculatelcs(str_1, str_2, m, n - 1);
         int b = calculatelcs(str_1, str_2, m - 1, n);
         int max = (a > b) ? a : b;
         arr[m - 1][n - 1] = max;
         return arr[m - 1][n - 1];
      }
   }
   public static void main(String[] args) {
      for (int i = 0; i < 1000; i++) {
         for (int j = 0; j < 1000; j++) {
            arr[i][j] = -1;
         }
      }
      String str_1 = "AGGTAB";
      String str_2 = "GXTXAYB";
      System.out.println("Length of LCS is " + calculatelcs(str_1, str_2, str_1.length(),str_2.length()));
   }
}

로그인 후 복사

Output

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Length of LCS is 4

로그인 후 복사

Method

메서드(calculatelcs)에 4개의 매개변수가 있는 것을 관찰했는데, 그 중 2개의 상수가 있습니다(상수는 그렇지 않습니다). 메모에 영향을 미침) 2개의 상수가 아닌 매개변수 (m 및 n)이 있으며, 해당 값은 메소드가 재귀적으로 호출될 때마다 변경됩니다. 메모이제이션을 달성하기 위해 arr[m-1][n-1]에 저장되는 lcs(m,n)의 계산된 값을 저장하는 2차원 배열을 도입합니다. 동일한 매개변수 m과 n을 사용하여 함수를 다시 호출하면 더 이상 재귀 호출을 수행하지 않고 이전에 계산된 lcs(m, n)이 다음 위치에 저장되었기 때문에 직접 arr[m-1][n-1]을 반환합니다. arr [m-1][n-1]이므로 재귀 호출 횟수가 줄어듭니다.

3차원 메모화

상수가 아닌 3개의 매개변수를 사용하는 재귀 프로그램을 위한 메모화 방법입니다. 여기서는 세 문자열의 LCS 길이를 예로 들어 계산합니다.

여기서 접근 방식은 주어진 문자열의 가능한 모든 하위 시퀀스(총 3ⁿ 가능한 하위 시퀀스가 있음)를 생성하고 그 중에서 가장 긴 공통 하위 시퀀스를 일치시키는 것입니다.

계산된 값을 저장하는 3차원 테이블을 소개하겠습니다. 하위 시퀀스를 고려하십시오.

A1[1...i] i < N
A2[1...j] j < M
A3[1...k] k <

그래서 위의 아이디어를 재귀 함수로 변환하면
f(N,M,K)={1+f(N -1,M-1,K-1)if (X[N] ==Y[M]==Z[K]최대(f(N-1,M,K),f(N,M-1, K),f(N,M,K-1))}
f(N-1,M,K) = X[i]를 예약하여 다른 문자를 재귀적으로 처리

f(N,M- 1,K) = Y[j]를 예약하여 다른 문자를 재귀적으로 처리

f(N,M,K-1) = Z[k]를 유지하여 다른 문자를 재귀적으로 처리

import java.io.IOException;
import java.io.InputStream;
import java.util.*;
class testClass {
   public static int[][][] arr = new int[100][100][100];
   static int calculatelcs(String str_1, String str_2, String str_3, int m, int n, int o) {
         for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
               arr[i][j][0] = 0;
            }
         }
         for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= o; j++) {
               arr[0][i][j] = 0;
            }
         }
         for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= o; j++) {
               arr[i][0][j] = 0;
            }
         }
         for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
               for (int k = 1; k <= o; k++) {
                  if (str_1.charAt(i - 1) == str_2.charAt(j-1) && str_2.charAt(j1) == str_3.charAt(k-1)) {
                     arr[i][j][k] = 1 + arr[i - 1][j - 1][k - 1];
                  }
                  else {
                     arr[i][j][k] = calculateMax(arr[i - 1][j][k], arr[i][j - 1][k], arr[i][j][k - 1]);
                  }
               }
            }
         }
         return arr[m][n][o];
   }
   static int calculateMax(int a, int b, int c) {
      if (a > b && a > c)
         return a;
         if (b > c)
         return b;
         return c;
   }
   public static void main(String[] args) {
      String str_1 = "clued";
      String str_2 = "clueless";
      String str_3 = "xcxclueing";
      int m = str_1.length();
      int n = str_2.length();
      int o = str_3.length();
      System.out.print("Length of LCS is " + calculatelcs(str_1, str_2, str_3, m, n, o));
   }
}

로그인 후 복사