About Algorithm4

알고리즘 04 Dynamic Programming

updated at 2022-04-01

Design

주어진 문제를(in natural language)
적절하게 Modeling 하고(in algorithmic steps)
Solution을 디자인(skeleton or pseudo code)
하는 과정에서, DP를 적용할 수 있음을 알 수 있는 property들이 있다.

1. Overlapping subproblems
   동적 프로그래밍은 동일한 하위 문제의 솔루션이 계속해서 필요할 때 주로 사용된다. 동적 프로그래밍에서 하위 문제에 대한 계산된 솔루션은 다시 계산할 필요가 없도록 테이블에 저장된다.
   이미 계산된 값을 저장하는 방법에는 두 가지가 있다.
   a) Memoized(Top down)
   b) Tabulated(Bottom up)

2. optimal substructure
   주어진 문제의 최적 솔루션(optimal solution)이 하위 문제의 최적 솔루션을 사용하여 얻을 수 있는 경우 주어진 문제는 최적 하위 구조 속성을 가진다.
   예를 들어, 최단 경로 문제(Shortest Path)는 다음과 같은 최적의 하위 구조 속성을 갖는다. 노드 x가 소스 노드 s에서 대상 노드 t까지의 최단 경로에 있으면, s에서 t까지의 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단 경로의 조합이 된다. Floyd-Warshall 과 같은 표준적인 APSP(All Pair Shortest Path) 알고리즘과 Bellman-Ford 와 같은 SSPA(Single Source Shortest Path) for negative weight edges 알고리즘은 DP의 전형적인 예이다.

Steps for Solution

Step1:

• establish a recursive property from the problem
• identify(find out, derive) a recurrence equation from the problem
• 큰 문제 = 작은 문제 + /* 작은 문제 + … + 작은 문제

Step2:

• solve in a bottom-up fashion programming
• solve smaller problems first(easy problem first)
• save them(smaller problems) in arrays(tables, dict…)
• use them later(from look-up tables)

Also called Save and Reuse Strategy!!!

Basic Steps

1. make examples(guessing)
2. recursive property = recurrence(in mathematical expression)
3. Save / Reuse

Good Examples

• binomial coefficients
• chained matrix multiplication

Binomial Coefficients

Binomial Coefficient 이항계수는 다음과 같은 linear equation으로 표현될 수 있다. n개 중에서 k개를 고르는, nCk의 조합 형태를 띄므로, nCk = (n,k)라 한다면, (n,k) = (n-1, k) + (n-1, k-1) when 0 < k < n 이 된다. 조합의 특성상, n == k, k ==0 인 경우에는 (n,k) == 1 이 된다.

이를 다음과 같은 linear recurrence equation으로 표현할 수 있다. B[n,k] = B[n-1,k] + B[n-1, k-1] if 0 < k < n B[n,k] = 1 if k == n, n == 0

이러한 표현의 형태는, 처음에 naive하게 접근하면 linear recurrence가 아닌 divide and conquer recurrence의 형태로 풀 수 있으나, 잘 보면, linear recurrence의 형태를 가지고 있고, subproblem overlapping이 심각하게 발생하므로 다른 접근 방법을 취할 필요가 있다는 것을 알 수 있다.

바론 Dynamic Programming approach 이다.

Dynamic programming이라고 하더라도 계산량이 많으면 full-exhaustive enumeration(brute force)와 같은 형태가 될 수 있으나, 중복 없이 필요한 연산만을 취한다는 부분에서 큰 차이가 있다.

DP는 필요한 subproblem의 계산 결과를 저장하고, bigger problem의 계산에 활용하다는 점에서 Save and Reuse strategy라고도 불린다.

class BinomialCoefficient:
    def __init__(self, n, k):
        self.look_up_table = [[0 for _ in range(k)] for _ in range(n)]
        self.calculate_Bnk(n, k)

    def calculate_Bnk(self, n, k):
        for i in range(n): # step 2
            for j in range(min(i, k)): # 전체를 반복하지 않는 것이 중요!!! 아예 계산 불가능한 부분도 있고, 계산이 불필요한 부분도 있다!!! 최적화에 있어 중요한 부분.
                if j == 0 or j == i:
                    self.look_up_table[i][j] = 1
                else:
                    self.look_up_table[i][j] = self.look_up_table[i-1][j-1] + self.look_up_table[i-1][j] # step 1
        return self.look_up_table[n][k]

Chained Matrix Multiplication

CMM(Chained Matrix Multiplication)은, 연속된 행렬의 결과를 구하는 식에서, 어떤 순서로 계산을 하는 것이 가장 작은 계산량을 가지는 지, 그 때의 계산량은 얼마인지를 구하는 문제이다.

행렬의 곱의 결과는 n x m 의 행렬이 되고, 이로 미루어 보아 행렬 곱은 두가지 변수로 대표되는, 2차원 배열에 계산 결과를 저장할 수 있음을 알 수 있다. 이 때 2차원 배열의 인덱스는, 행렬의 곱셈에서, 모든 곱셈을 마치면 중간 행렬은 사라지고, 처음 행렬의 행 x 마지막 행렬의 열의 결과로 귀결된다는 점에서 [처음 행렬의 행][마지막 행렬의 열] 과 같이 사용할 수 있음을 알 수 있다.

임의의 개수의 행렬 곱을 계산하는 과정을 직접 손으로 해보면, 규칙을 찾을 수 있는데, 이 때 중요한 점은 가장 쉬운(작은) 문제를 푸는 것 부터 시작해야 한다는 것이다. 그래야 DP의 과정을 경험적으로 이해하기 쉽고, 이를 linear recurrence equation으로 표현하기 쉬워진다.

경험적으로 찾은 CMM의 recurrence equation은 다음과 같다. M[i,j] = min(M[i,k] + M[k+1, j] + C(i-1)C(k)C(j) for i <= k <= j-1) M[i,i] = 0

이러한 과정은 DP의 solution steps 0. check examples(guessing)

1. find recursive property => recurrence in mathmatical expression
2. save and reuse 중

0, 1 번째 스텝에 해당한다.

save and reuse 기법을 사용하지만, 연산량이 많은 경우에는, running time에서의 시간 최적화를 위해 code optimization이 필요하다.

class DP_CMM:
    def __init__(self, matricies_sequence, dimension_row_col):
        self.lookup_table = [[0 for _ in range(len(matricies_sequence))] for _ in range(len(matricies_sequence))]
        self.calculate_min_cmm(matricies_sequence, dimension_row_col)

    def calculate_min_cmm(self, matricies_sequence, dimension_row_col):
        for i in range(len(matricies_sequence)):
            for j in range(len(matricies_sequence)):
                if i == j:
                    self.lookup_table[i][j] = 0
                else:
                    minimum_calculation = sys.maxsize
                    for k in range(i, j-1):
                        calculation = self.lookup_table[i,k] + self.lookup_table[k+1,j] + dimension_row_col[i-1].col * dimension_row_col[k].col * dimension_row_col[j].col
                        if calculation < minimum_calculation:
                            minimum_calculation = calculation
                    self.lookup_table[i][j] = minimum_calculation
        return self.lookup_table[0][len(matricies_sequence)]