15. Dynamic Programming

동적 계획법은 분할 정복과 비슷하게 부분 문제를 모아 문제를 해결한다. 차이점은, 분할 정복은 원본 문제를 서로 겹치지 않는 부분 문제로 나누는 반면 동적 계획법은 부분 문제들이 겹칠 때 겹치는 부분문제들을 한 번만 해결함으로써 재계산을 줄인다. 동적 계획법은 주로 최적화 문제에 사용되며, 다음의 4단계로 나뉜다:

  1. 최적해의 구조를 특정한다.
  2. 최적해의 값을 재귀적으로 정의한다.
  3. 최적해의 값을 바닥에서부터 위로 계산한다.
  4. 계산된 정보로부터 최적해를 구성한다.

최적해의 값에만 관심이 있다면 4번째 단계는 필요가 없다. 4번째 단계를 수행할 때 3번째 단계에서 유용한 정보가 있다면 따로 저장해 두기도 한다.

15.1. Rod cutting

첫 번째 예는 쇠 막대 분할 문제이다. n인치의 쇠 막대가 있고 i = 1, …, n마다 가격 p_i가 매겨져 있을 때, 쇠 막대로부터 가장 많은 이윤을 남기는 분할법을 찾는 것이다. 자르는 방법은 2^(n-1) 가지의 서로 다른 방법이 있다. 이 때 눈여겨보아야 할 점은 n인치의 쇠 막대를 풀 때 우리는 동일한 종류의 더 작은 부분 문제를 푼다는 점이다. 즉, 최적 부분구조가 존재하여, 최적해는 관계된 부분 문제의 최적해로 구성되어 있다는 것이다.

Recursive top-down implementation

이로부터 다음과 같은 알고리즘을 구성 가능하다.

CUT-ROD(p, n)
if n == 0
    return 0
q = -∞
for i = 1 to n
    q = max(q, p[i] + CUT-ROD(p, n - i))
return q

그러나 이는 비효율적이다. CUT-ROD는 같은 k에 대해 부분 문제 CUT-ROD(p, k)를 계속해서 풀기 때문이다. 이 때 동작 시간은 2^n이 된다.

Using dynamic programming for optimal rod cutting

동적 계획법은 이미 푼 부분문제의 값을 추가 메모리를 사용해 저장해서 계산 시간을 절약한다 (메모리-시간 트레이드오프). 각각의 부분문제를 다항 시간에 풀 수 있고 서로 다른 부분 문제의 수가 입력의 크기에 대해 다항식이면 동적 계획법은 다항 시간에 푸는 것이 가능하다.

동적 계획법은 각각의 부분문제를 저장해 두는 상-하 방향과 메모이제이션 방법과 작은 부분문제들을 저장해 가면서 풀면서 부분 문제로부터 전체 문제를 구성해 나가는 하-상 방향 의 두 가지 방법이 있다. 첫 번째 방식의 구현은 다음과 같다.

MEMOIZED-CUT-ROD(p, n)
Let r[0, ..., n] be a new array
for i = 0 to n
    r[i] = -∞
return MEMOIZED-CUT-ROD-AUX(p, n, r)

MEMOIZED-CUT-ROD-AUX(p, n, r)
if r[n] ≥ 0
    return r[n]
if n == 0
    q = 0
else
    q = -∞
    for i = 1 to n
        q = max(q, p[i] + MEMOIZEED-CUT-ROD-AUX(p, n - i, r))
r[n] = q
return q

하-상 방향은 조금 더 간단하다.

BOTTOM-UP-CUT-ROD(p, n)
Let r[0, ..., n] be a new array
r[0] = 0
for j = 1 to n
    q = -∞
    for i = 1 to j
        q = max(q, p[i] + r[j - i])
    r[j] = q
return r[n]

둘 모두 수행 시간은 \Theta(n^{2})로 같다.

Subproblem graphs

부분 문제 그래프는 동적 계획법에서 부분 문제간의 의존 관계를 나타낸 그래프이다. 부분 문제 그래프의 크기는 수행 시간을 판단하는 데 도움이 된다. 부분 문제를 푸는 데 걸리는 시간은 외차수와 비례하며, 부분 문제의 수는 정점의 수와 같다. 대개, 동적 계획법의 수행 시간은 부분 문제 그래프의 정점과 간선의 수에 대해 선형이다.

Reconstructing a solution

동적 계획법을 확장해 최적해를 직접 구성할 수 있다.

EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
Let r[0, ..., n] and s[1, ..., n] be new arrays
r[0] = 0
for j = 1 to n
    q = -∞
    for i = 1 to j
        if q < p[i] + r[j - i]
            q = p[i] + r[j - i]
            s[j] = i
    r[j] = q
return r and s

PRINT-CUT-ROD-SOLUTION(p, n)
(r, s) = EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
while n > 0
    print s[n]
    n = n - s[n]

15.2. Matrix-chain multiplication

두 번째 문제는 여러 행렬을 어떤 순서로 곱해야 가장 게산량이 적을지에 대한 것이다. 행렬 곱은 다음과 같이 이루어진다.

MATRIX-MULTIPLY(A, B)
if A.columns ≠ B.rows
    error "incompatible dimensions"
else
    let C be a new A.rows x B.columns matrix
    for i = 1 to A.rows
        for j = 1 to B.columns
            c_ij = 0
            for k = 1 to A.columns
                c_ij += a_ik * b_kj
    return C

행렬 A와 B는 호환 가능해야만 곱할 수가 있다. 연속된 호환 가능한 행렬이 있을 때, 이들을 어떤 순서로 곱하느냐가 전체 연산량에 큰 영향을 준다. 행렬-연쇄곱 문제는 가장 연산량을 적게 하는 곱 순서를 찾는 것이다.

Counting the number of parenthesizations

전체 경우의 수는 P(n) = \sum_{k=1}^{n-1} P(k) P(n-k)의 점화식으로 나타내어지는데, 이는 카탈란 수로서 \Omega(\frac{4^{n}}{n^{\frac{3}{2}}}의 속도로 증가한다. 그러므로 완전 탐색은 비효율적이다.

Applying dynamic programming

동적 계획법을 적용하면 다음과 같다.

MATRIX-CHAIN-ORDER(p)
n = p.length - 1
Let m[1-n, 1-n] and s[1-(n-1), 2-n] be new tables
for i = 1 to n
    m[i][i] = 0
for l = 2 to n // l is the chain length
    for i = 1 to n - l + 1
        j = i + l - 1
        m[i][j] = ∞
        for k = i to j - 1
            q = m[i][k] + m[k + 1][j] + p_(i-1)p_k p_j
            if q < m[i][j]
                m[i][j] = q
                s[i][j] = k
return m and s

PRINT-OPTIMAL-PARENS(s, i, j)
if i == j
    print "A_i"
else
    print "("
    PRINT-OPTIMAL-PARENS(s, i, s[i][j])
    PRINT-OPTIMAL-PARENS(s, s[i][j] + 1, j)
    print ")"

수행 시간은 O(n^{3})이다.

15.3. Elements of dynamic programming

그래서 동적 계획법을 언제 쓸 수 있는 것인가?

Optimal substructure

최적의 부분 구조가 있어야 한다. 즉, 전체 문제를 똑같은 종류의 더 작은 크기의 부분문제들을 이용해 풀 수 있어야 한다.

Subtleties

동적 계획법을 적용할 수 없는 예가 있다. 비가중 최단 경로 문제는 동적 계획법을 적용할 수 있지만, 비가중 최장 단순 경로 문제는 적용할 수 없다. 왜냐하면 최장 단순 경로를 찾는 부분 문제는 독립적이지 않기 때문이다. 즉, 최단 경로 문제와는 다르게, 한 부분 문제의 해가 다른 부분 문제에 영향을 끼친다.

Overlapping subproblems

동적 계획법이 효과적일 때에는 부분 문제가 겹칠 때이다. 아니면 분할 정복이 더 낫다. 다음의 재귀적 해는 지수적 시간을 갖는다.

RECURSIVE-MATRIX-CHAIN(p, i, j)
if i == j
    return 0
m[i][j] = ∞
for k = i to j - 1
    q = RECURSIVE-MATRIX-CHAIN(p, i, k) + RECURSIVE-MATRIX-CHAIN(p, k + 1, j) + p_(i-1)p_(k)p_(j)
    if q < m[i][j]
        m[i][j] = q
return m[i][j]

Reconstructing an optimal solution

동적 계획법을 쓸 때 최적해를 구성하기 위해 중간 결과들을 미리 저장해둘 수 있다.

Memoization

상-하 방향 동적 계획법에서는 메모이제이션으로 부분 문제를 저장해둘 수 있다.

MEMOIZED-MATRIX-CHAIN(p)
n = p.length - 1
Let m[1-n, 1-n] be a new table
for i = 1 to n
    for j = 1 to n
        m[i][j] = ∞
return LOOKUP-CHAIN(m, p, 1, n)

LOOKUP-CHAIN(m, p, i, j)
if m[i][j] < ∞
    return m[i][j]
if i == j
    m[i][j] = 0
else
    for k = 1 to j - 1
        q = LOOKUP-CHAIN(m, p, i, k) + LOOKUP-CHAIN(m, p, k + 1, j) + p_(i-1)p_(k)p_(j)
    if q < m[i][j]
        m[i][j] = q
return m[i][j]

15.4. Longest common subsequence

염기 서열 연구 문제 중 두 순열의 부분열들 중 공통 부분열 중 가장 긴 것을 찾는 최장 공통 부분열 문제가 있다. 이는 동적 계획법으로 풀 수 있다.

Theorem 15.1. X = (x_{1}, \cdots, x_{m}), Y = (y_{1}, \cdots, y_{n})이 있고 Z = (z_{1}, \cdots, z_{k})이 X, Y의 최장 공통 부분열이면,

  • x_{m} = y_{n}이면 z_{k} = x_{m} = y_{n}이고 Z_{k-1}X_{m-1}Y_{n-1}의 최장 공통 부분열이다.
  • x_{m} \neq y_{n}이면 z_{k} \neq x_{m}일 경우 Z는 X_{m-1}과 Y의 최장 공통 부분열이다.
  • x_{m} \neq y_{n}이면 z_{k} \neq y_{n}일 경우 Z는 X와 Y_{n-1}의최장 공통 부분열이다.

이에 동적 계획법을 적용해 풀면 다음과 같다.

LCS-LENGTH(X, Y)
m = X.length
n = Y.length
Let b[1-m, 1-n] and c[0-m, 0-n] be new tables
for i = 1 to m
    c[i][0] = 0
for j = 0 to n
    c[0][j] = 0
for i = 1 to m
    for j = 1 to n
        if x_i == y_j
            c[i][j] = c[i - 1][j - 1] + 1
            b[i][j] = ↖
        else if c[i - 1][j] ≥ c[i][j - 1]
            c[i][j] = c[i - 1][j]
            b[i][j] = ↑
        else
            c[i][j] = c[i][j - 1]
            b[i][j] = ←
return c and b

PRINT-LCS(b, X, i, j)
if i == 0 or j == 0
    return
if b[i][j] == ↖
    PRINT-LCS(b, X, i - 1, j - 1)
    print x_i
else if b[i][j] == ↑
    PRINT-LCS(b, X, i - 1, j)
else
    PRINT-LCS(b, X, i, j - 1)

15.5. Optimal binary search trees

단어 검색을 위한 이진 탐색 트리를 만들 때 단어의 빈도 수를 안다고 할 때 탐색하는 전체 노드의 수를 최소화하는 문제를 최적 이진 탐색 트리 문제라 한다. 이는 동적 계획법으로 다음과 같이 풀 수 있다.

OPTIMAL-BST(p, q, n)
Let e[1-(n+1), 0-n], w[1-(n+1), 0-n], root[1-n, 1-n] be new tables
for i = 1 to n + 1
    e[i][i - 1] = q_(i-1)
    w[i][i - 1] = q_(i-1)
for l = 1 to n
    for i = 1 to n - l + 1
        j = i + l - 1
        e[i][j] = ∞
        w[i][j] = w[i][j - 1] + p_j + q_j
        for r = i to j
            t = e[i][r - 1] + e[r + 1][j] + w[i][j]
            if t < e[i][j]
                e[i][j] = t
                root[i][j] = r
return e and root

수행 시간은 O(n^{3})이다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중