15 Dynamic Programming15.1 Rod Cutting15.2 Matrix-chain multiplicationCouting the number of parenthesizations15.3 Elements of dynamic programmingOptimal substructureOverlapping subproblemsReconstructing an optimal solutionMemoization15.4 Longest common subsequenceStep 1 : Characterizing a longest common subsequenceTheorem 15.1 (Optimal substructure of an LCS)Step 2: A recursive solutionStep 3 : Computing the length of an LCSStep 4 : Constructing an LCSImproving the code15.5 Optimal binary search treesStep 1 : The structure of an optimal binary search treeStep 2: A recursive solutionStep 3: Computing the expected search cost of an optimal binary search tree

 

15 Dynamic Programming

 

 

15.1 Rod Cutting

 

 

15.2 Matrix-chain multiplication

dynamic programming의 다음 예제는 matrix-chain multiplication의 문제를 푸는 알고리즘이다. 우리는 곱해질 n개의 행렬에 대한 한 sequence (chain) $\langle A_1, A_2, \dots, A_n \rangle$가 주어지고, 우리는 그 곱인 다음을 연산하고 싶어한다

$$A_1,A_2\cdots A_n.\;\; (15.5)$$

우리는 그 행렬들이 서로 곱해지는 방식에서 모든 애매함을 해결하기 위해 괄호화 한다면, 행렬들의 쌍들을 곱하기 위한 standard algorithm을 한 subroutine으로 사용하여 그 식 (15.5)를 evaluate할 수 있다. 행렬 곱은 associative하고, 그래서 모든 괄호는 같은 결과를 만들어낸다. 행렬곱은 만약 그것이 single matrix이거나 두 개의 완전히 괄호가 쳐진 행렬곱의 곱이라면, 완전히 괄호화된다 (fully parenthesized). 예를들어, 만약 그 행렬의 chain이 $\langle A_1, A_2, A_3, A_4 \rangle$이라면, 우리는 5개의 다른 방식으로 그 곱 $A_1A_2A_3A_4$를 괄호를 칠 수 있다:

$$\begin{split} & (A_1(A_2(A_3A_4))), \\ & (A_1((A_2A_3)A_4)), \\ & ((A_1A_2)(A_3A_4)), \\ & ((A_1(A_2A_3))A_4), \\ & (((A_1A_2)A_3)A_4). \end{split}$$

우리가 행렬의 한 chain을 괄호치는 방법은 그 곱을 구하는 비용에 극적인 영향을 가질 수 있다. 두 행렬의 곱의 비용을 처음에 고려해라. 표준 알고리즘은 다음의 의사코드에 의해 주어지는데, 이것은 Section 4.2에서 SQUARE-MATRIX-MULTIPLY procedure를 일반화한다. 그 attributes rows와 columns은 한 행렬에서 rows와 columns의 개수이다.

MATRIX-MULTIPLAY(A, B)
1   if A.columns != B.rows
2       error "incompatible dimensions"
3   else let C be  a new A.rows X B.column matrix
4       for i = 1 to A.rows
5           for j = 1 to B.columns
6               c_ij = 0
7               for k = 1 to A.columns
8                   c_ij = c_ij + a_ik * b_kj
9   return C

우리는 두 행렬 A와 B를 그것들이 compatible하다면 곱할 수 있다 : A의 열의 개수는 B의 행의 개수와 같아야 한다는 것이다. 만약 A가 $p \times q$ 행렬이고, B가 $q \times r$ 행렬이라면, 그 최종 행렬 $C$는 $p \times r$ 행렬이다. $C$를 계산하는 시간은 line 8에 있는 scalar 곱의 개수에 의해 지배된다. 그리고 이 개수는 $pqr$이다. 다음에는, 우리는 scalar 곱의 개수의 관점에서 비용들을 표현할 것이다.

행렬곱의 다른 괄호화에 의해 발생하는 다른 비용을 보여주기 위해, 세 개의 행렬의 한 chain $\langle A_1, A_2, A_3 \rangle$의 문제를 고려해라. 행렬의 dimensions이 각각 $10 \times 100$, $100 \times 5$, 그리고 $5 \times 50$이라고 가정하자. 만약 $((A_1A_2)A_3)$에 따라 곱한다면, 우리는 $10 \times 5$ maxtir product인 $A_1A_2$를 계산하기 위해 $10 \cdot 100 \cdot 5 = 5000$의 스칼라 곱을 수행한다. 더해서 이 행렬를 $A_3$로 곱하기 위해 $10 \cdot 5 \cdot 50 = 2500$ 스칼라 곱이 더해진다. 총 7500번의 스칼라 곱이다. 만약 대신에 우리가 $(A_1(A_2A_3))$의 괄호화로 곱을 한다면, 우리는 $100 \times 50$의 행렬곱 $A_2A_3$를 계산하기 위해 $100 \cdot 5 \cdot 50 = 25,000$ 스칼라 곱을 수행한다. 거기에 $A_1$를 이 행렬로 곱하기 위해 $10 \cdot 100 \cdot 50 = 50,000$ 스칼라 곱이 더해진다. 총 $75,000$번의 스칼라곱이다. 따라서 첫 번째 괄호화를 따라 곱하는 것이 10배 더 빠르다.

우리는 matrix-chain multiplication problem을 다음과 같이 명시한다 : n개의 행렬의 한 chain $\langle A_1, A_2, \dots, A_n \rangle$이 주어진다면, $i = 1, 2, \dots, n$에 대해, 행렬 $A_i$는 $p_{i-1} \times p_{i}$의 dimension을 가진다면, 스칼라곱의 개수를 최소화 하는 방식으로 $A_1A_2\cdots A_n$의 곱을 완전히 괄호화해라.

matrix-chain multiplication problem에서, 우리가 실제로 행렬을 곱하고 있지 않다는 것에 주목해라. 우리의 목적은 가장 낮은 비용을 가진 행렬 곱을 위한 순서를 결정짓는 것 뿐이다. 일반적으로 이 최적의 순서를 결정할 때 소요되는 시간은 (75,000 대신에 7500 스칼라곱만을 수행하는 것 같은) 실제로 행렬곱을 수행할 때 나중에 절약되는 시간에 의해 지불되는 것보다 더 크다.

 

Couting the number of parenthesizations

dynamic programming으로 matrix-chain multiplication 문제를 풀기전에, 모든 가능한 괄호화를 완전 체크하는 것이 효율적인 알고리즘을 만들지 않는다는 것을 우리 자신에게 설득해보자. n개의 행렬의 한 sequence의 번갈아가면서 괄호화 하는 것의 개수를 $P(n)$으로 표기하자. $n = 1$일 때, 우리는 한 개의 행렬을 가지고, 그러므로 그 행렬곱을 fully parenthesize하는 한 가지 방법만을 가진다. $n \geq 2$일 때, fully parenthesized matrix product는 두 개의 fully parenthesized matrix subproduct의 곱이고, 두 개의 subproducts사이의 분리는 어떤 $k = 1, 2, \dots, n - 1$에 대해 $k$번째와 $(k+1)$번째 사이에 발생할지도 모른다. 따라서, 우리는 다음의 반복을 얻게 된다

$$P(n) = \bigg\{ \begin{split} & 1 &\; \text{if $n = 1$,} \\ & \sum^{n-1}_{k=1}P(k)P(n-k) & \; \text{if $n \geq 2$.} \end{split} \\ (15.6)$$

Problem 12-4는 비슷한 반복에 대한 solution이 $\Omega(4^n/n^{3/2})$으로 자라는 Catalan numbers라는 것을 보여달라고 요청한다. 더 간단한 exercise (see Exercise 15.2-3)는 recurrence (15.6)에 대한 해가 $\Omega(2^n)$이라는 것을 보여준다. 해의 개수는 따라서 n에 exponential하고, exhaustive search의 brute-force method는 matrix chain의 optimally parenthesize를 하는 방법을 결정할 때 좋지 않은 전략을 만든다.

 

15.3 Elements of dynamic programming

비록 우리가 dynamic-programming의 두 예제들을 풀어보았을지라도, 너는 여전히 그 방법들이 언제 적용되는지가 궁금할지도 모른다. 엔지니어링 관점에서, 우리는 언제 한 문제에 대해 dynamic-prgramming solution을 찾아야 하는가? 이 섹션에서, 우리는 dynamic programming이 적용되게 하기 위해, 가져야 하는 두 가지 주요한 재료들을 조사한다 : optimal substructure와 overlapping subproblems. 우리는 또한 memoization이 top-down recursive approach에서 overlapping-subproblems property를 이용하게 도와주는 방법을 다시 알아보고 이야기 한다.

 

Optimal substructure

dynamic programming으로 한 optimization problem을 해결하는 것의 첫 번째 단계는 optimal solution의 구조를 특징화 하는 것이다. 만약 한 문제에 대한 optimal solution이 그것 내에서 subproblems에 대한 optimal solutions을 포함한다면 그 문제가 optimal substructure를 보여준다고 회상해라. 한 문제가 optimal substructure를 보여줄 때 마다, 우리는 dynamic programming이 적용될지도 모르는 좋은 단서를 가진다. (Chapter 16에서 이야기 하듯이, 그러나 greedy strategy가 적용될 수 있다는 것을 의미할지도 모른다.) dynamic programming에서, 우리는 subproblems에 대한 optimal solutions으로부터 문제에 대한 optimal solution을 구성한다. 결과적으로, 우리는 우리가 고려하는 subproblems의 범위가 optimal solution에서 사용되는 것을들 포함하는 것을 보장하도록 신경써야 한다.

우리는 이제까지 보았던 문제들 둘 다에서 optimal substructure를 발견했었다. Section 15.1에서, 우리는 길이가 n인 막대를 자르는 최적의 방법은 (만약 우리가 어떤 cuts을 만들든 간에) 첫 번째 cut으로부터 원인이 되는 두 조각들을 최적으로 자르는 것을 포함한다. Section 15.2에서, $A_k$와 $A_{k+1}$사이의 곱을 분리하는 $A_i A_{i+1}, \cdots, A_j$의 optimal parenthesization은 그것 내에서 $A_i A_{i+1} \cdots A_k$와 $A_{k+1}, A_{k+2} \cdots A_j$를 parenthesizing하는 것의 문제에 대한 optimal solutions을 포함한다.

너는 스스로 optimal substructure를 발견하는 것에서 한 공통 패턴을 발견하게 될 것이다:

1. 너는 그 문제에 대한 한 솔루션이 선택을 하는 것으로 구성된다는 것을 보여준다. 그 선택은 그 matrix chain을 분리하는 index를 선택하거나 rod에서 초기 cut을 선택하는 것과 같은 선택이다. 이 선택을 하는 것은 해결해야 할 한 개 이상의 subproblems을 남긴다.
2. 너는 주어진 문제에 대해, optimal solution을 이끄는 선택을 받는다고 가정한다. 너는 이 선택을 결정하는 방법에 대해 아직 걱정하지 않는다. 너는 그것이 너에게 주어진다고 가정한다.
3. 이 선택이 주어진다면, 너는 어떤 subproblems이 뒤따를지를 결정하고, subproblems의 최종 space를 가장 잘 특징화 하는 방법을 결정한다.
4. 너는 문제에 대한 optimal solution 내에서 사용되는 subproblems에 대한 solutions들이 그것들 스스로 "cut-and-paste" 방법을 사용해서 optimal해진다는 것을 보여준다. 너는 그 subproblem solutions 각각이 optimal 하지 않다고 가정하고, 모순을 도출하여 그렇게 한다. 특히, 각 subproblem에 대해 nonoptimal solution을 "cutting out"하고, optimal one으로 "pasting in"하여, 원래 문제에 대해 더 좋은 해결책을 얻을 수 있다는 것을 보여주고, 따라서 너가 이미 optimal solution을 가졌다는 너의 가정을 반박한다. 만약 한 optimal solution이 한 개 이상의 subproblem에 대해 발생한다면, 그것들은 일반적으로 너가 적은 노력으로 다르 ㄴ것들에 적용할 수 있는 cut-and-paste argument를 수정할 수 있다는 것과 비슷하다.

subproblems의 space를 특징화 하기 위해, 좋은 경험의 법칙은 그 space를 가능한한 간단하게 유지하고, 그러고나서 필요한 만큼 확장하라고 말한다. 예를들어, rod-cutting problem에서 우리가 고려했던 subproblems의 space는 각 size가 i인 길이가 i의 한 막대를 최적으로 자르는 것의 문제를 포함했다. 이 subproblem space는 잘 작동했었고, 그리고 우리는 subproblems의 좀 더 일반적인 space를 시도할 필요가 없었다.

반대로, 우리가 matrix-chain multiplication에 대한 우리의 subproblem space를 $A_1A_2 \cdots A_j$의 형태로 matrix products로 제한하려고 했다고 가정하자. 이전처럼, 한 optimal parenthesization은 어떤 $1 \leq k < j$에 대해 $A_k$와 $A_{k+1}$사이의 이 곱을 분리해야 한다. 만약 우리가 $k$가 항상 $j - 1$과 같다고 보장할 수 없다면, 우리는 $A_1A_2 \cdots A_K$와 $A_{k+1} A_{k+2} \cdots A_j$의 형태의 subproblems을 가진 것을 알게 되고, 그 후자의 subproblem은 $A_1A_2 \cdots A_j$의 형태가 아니다. 이 문제에 대해, 우리는 우리의 subproblems이 "both ends"(양쪽 끝)에서 가변하도록 할 필요가 있다. 즉, $i$와 $j$가 subproblem $A_iA_{i+1}\cdots A_j$ 에서 변하도록 하는 것이다.

Obtimal substructure는 두 가지 방식에서 problem domains에 걸쳐서 변한다:

1. original problem에 대한 optimal solution이 얼마나 많은 subproblems을 사용하는가, 그리고
2. optimal solution에서 어떤 subproblem(s)를 사용하맂를 결정할 때 우리가 얼마나 많은 선택권을 가지는가.

rod-cutting problem에서, size n인 한 rod를 자르는 것에 대한 optimal solution은 그냥 한 subproblem ($n - i$ size의)를 사용하지만, 우리는 어떤 것이 optimal solution을 만들어내는지를 결정하기 위해 $i$에 대해 n개의 choices들을 고려해야 한다. subchain $A_iA_{i+1} \cdots A_j$에 대한 Matrix-chain multiplication은 두 개의 subproblems과 $j - i$의 choices를 가진 예시의 역할을 한다. 우리가 그 곱을 분리하는 주어진 행렬 $A_k$에 대해, 우리는 두 개의 subproblems을 가진다 - $A_i A_{i+1} \cdots A_k$ 괄호치는 것과 $A_{k+1} A_{k+2} \cdots A_j$를 괄호치는 것 - 우리는 그것들 둘 다를 optimally하게 해결해야만 한다. 우리가 subproblems에 대한 optimal solutions을 결정한다면, 우리는 그 index k에 대해 $j - i$의 candidates 중에서 선택한다.

비공식적으로, dynamic-programming 알고리즘의 작동 시간은 두 요소의 곱에 의존한다 : 전체 subproblems의 개수와 각 subproblem에 대해 우리가 얼마나 많은 choices를 보는지. rod cutting에서, 우리는 전체 $\Theta(n)$의 subproblems을 가졌고, 각각에 대해 조사해야 할 최대 n개의 choices들을 가졌고, 이것은 $O(n^2)$ running time을 만들어낸다. Matrix-chain multiplication은 전체 $\Theta(n^2)$의 subproblems 가졌고, 그리고 각각에서, 우리는 최대 $n - 1$개의 choices을 가졌고, 이것은 $O(n^3)$ running time을 준다 (실제로 $\Theta(n^3)$ running time이다. Exercise 15.2-5)

보통, subproblem graph는 같은 분석을 수행하는 대안의 방법을 준다. 각 정점은 subproblem에 대응되고, subproblem에 대한 choices들은 그 subproblem에 들어가는 edges이다. rod cutting에서 subproblem graph가 n개의 정점을 가졌고, 정점마다 최대 n개의 edges를 가졌다는 것을 회상해라. 이것은 $O(n^2)$의 running time을 준다. matrix-chain multiplication에 대해, 만약 우리가 subproblem graph를 그린다면, 그것은 $\Theta(n^2)$의 vertices를 가질 것이고, 각 vertex는 최대 $n - 1$의 degree를 가지고, 총 $O(n^3)$ vertices와 edges를 준다.

Dynamic programming은 종종 bottom-up 방식으로 optimal substructure를 사용한다. 즉, 우리는 처음에 subproblems에 대한 optimal solutions을 찾고, 그 subproblems들을 해결하여, 우리는 그 문제에 대한 optimal solution을 찾는다. 문제에 대한 optimal solution을 찾는 것은 문제를 풀 때 우리가 어떤 것을 사용할지에 대한 subproblems사이에서의 선택을 하는 것을 수반한다. problem solution의 비용은 보통 subproblem costs와 그 선택에 직접적으로 원인이 되는 비용을 더한다. rod cutting에서, 예를들어, 처음에 우리는 $i = 0, 1, \dots, n - 1$에 대해 $i$의 길이를 가진 rods를 자르는 optimal ways를 결정하는 것의 subproblems를 해결했고, 그러고나서 어떤 그러한 subproblem이 길이가 n의 막대에 대한 optimal solution을 만들었는지를 결정했다, 방정식 (15.2)를 사용하여. 그 선택 자체에 원인이 되는 비용은 방정식 (15.2)에 있는 항 $p_i$이다. matrix-chain multiplication에서, 우리는 $A_i A_{i+1} \cdots A_{j}$ subchains의 optimal parenthesizations을 결정했고, 그러고나서 우리는 그 곱을 분리할 행렬 $A_k$를 선택했다. 그 선택 자체의 원인이 되는 비용은 그 항$p_{i-1}p_k p_j$이다.

Chapter 16에서, 우리는 "greedy algorithms"을 조사할 것인데, 이것은 dynamic programming과 많은 유사성을 가진다. 특히, 어떤 greedy algorithms이 적용되는 문제들은 optimal substructure를 가진다. greedy algorithms과 dynamic programming 사이의 한 가지 중요한 차이는, subproblems에 대한 optimal solutions을 처음에 찾고나서, 그러고나서 알려진 선택을 하는 것 대신에, greedy algorithms은 처음에 "greedy" choice를 한다 - 그 시기에 가장 좋게 보이는 선택이다 - 그러고나서 최종 subproblem을 해결하는데, 모든 가능한 관련된 더 작은 subproblems을 해결하는데 문제가 없다. 놀랍게도, 어떤 경우들에서 이 전략은 작동한다.

 

Subtleties

너는 optimal substructure가 적용되지 않을 때, 적용된다고 가정하지 않도록 주의해야 한다. 우리가 directed graph $G = (V, E)$와 정점 $u, v \in V$가 주어진 다음의 두 문제를 고려해보자.

Unweighted shortest path:¹ 가장 적은 edges로 구성된 $u$에서 $v$로 가는 경로를 찾아라. 그러한 path는 simple해야하는데, path에서 cycle를 제거하는 것은 더 적은 edges를 가진 path를 만들기 때문이다.

---

Unweighted longest simple path: 가장 많은 edges로 구성된 $u$에서 $v$로 가는 simple path를 찾아라. 우리는 simplicity의 요구사항을 포함할 필요가 있다. 왜냐하면, 그렇지 않다면, 우리는 임의의 큰 개수의 edges를 가진 paths를 만들고 싶은 만큼 cycle을 탐색할 수 있기 때문이다.

그 unweighted shortest-path problem은 optimal substructure를 다음과 같이 보여준다. $u \neq v$라고 가정하자, 그 문제가 nontrivial이게 하기 위해서. 그러고나서, $u$에서 $v$로 가는 어떤 경로 $p$는 중간 정점, 가령 $w$를 포함해야만 한다. ($w$는 $u$ 또는 $v$일지도 모른다.) 따라서, 우리는 $u \leadsto^p v$를 $u \leadsto^{p_1} w \leadsto^{p_2} v$의 subpaths로 분해할 수 있다. 명백히, p에서 edges의 개수는 $p_1$에서의 edges의 개수와 $p_2$의 edges의 개수를 합한 것과 같다. 만약 $p$가 $u$에서 $v$로 가는 optimal (즉, 가장 짧은) path라면, 그러면 $p_1$은 $u$에서 $w$로 가는 가장 짧은 path여야 한다고 우리는 주장한다. 왜? 우리는 "cut-and-paste" 주장을 사용한다: 만약 다른 경로가 있다면, 가령 $p'_1$, $p_1$보다 더 작은 edges를 가진 $u$에서 $w$로 가는, 그러고나서 우리는 $p_1$를 자르고 $p$보다 더 작은 edges를 가진 경로 $u \leadsto^{p'_1} w \leadsto^{p_2} v$를 만들기 위해 $p'_1$를 paste할 수 있다, 그리고 따라서 이것은 $p$의 optimality를 반박한다. 대칭적으로, $p_2$는 $w$에서 $v$로 가는 shortest path여야 한다. 따라서, 우리는 모든 중간 정점 $w$를 고려하여 $u$에서 $v$로 가는 최단 경로를 발견할 수 있고, $u$에서 $w$로 가는 최단 경로와 $w$에서 $v$로 가는 최단 경로를 발견하고, 최종 최단 경로를 만들어내는 중간 정점 $w$를 선택한다. Section 25.2에서, 우리는 weighted, directed graph에서 정점들의 모든 쌍 사이의 최단 경로를 찾기 위해 optimal substructure의 이 관찰의 변형을 사용한다.

unweighted longest simple path를 찾는 문제가 또한 opitmal substructure를 보여줄 거라 가정하는 것이 유혹적일지도 모른다. 결국, 만약 우리가 logest simple path $u \leadsto^p v$ 를 subpaths $u \leadsto^{p_1} w \leadsto^{p_2} v$로 분해한다면, 그러면 $p_1$은 $u$에서 $w$로 가는 longest simple path이고, $p_2$는 $w$에서 $v$로 가는 longset simple path여야 하지 않는가? 그 답은 no이다. 그림 15.6이 한 예시를 제공한다. 경로 $q \rightarrow r \rightarrow t$를 고려해라. 그리고 이것은 $q$에서 $t$로 가는 가장 긴 simple path이다. $q \rightarrow r$은 $q$에서 $r$로 가는 가장 긴 simple path인가? 아니다, 더 긴 simple path는 $q \rightarrow s \rightarrow t \rightarrow r$ 경로이다. $r \rightarrow t$는 $r$에서 $t$로 가는 longest simple path인가? 또 다시 아니다. 더 긴 simple path는 $r \rightarrow q \rightarrow s \rightarrow t$ 경로이다.

이 예제는 longest simple paths에 대해, 그 문제가 optimal substructure가 부족할 뿐만 아니라, 우리가 반드시 subproblems에 대한 solutions으로부터 그 문제에 대한 "legal" solution을 모을 수 없다는 것을 보여준다. 만약 우리가 logest simple path $q \rightarrow s \rightarrow r \rightarrow t$와 $r \rightarrow q \rightarrow s \rightarrow t$를 합한다면, 우리는 경로 $q \rightarrow s \rightarrow t \rightarrow r \rightarrow q \rightarrow s \rightarrow t$를 얻게되고, 이것은 simple하지 않다. 정말로, unweighted longest simple path를 발견하는 것의 문제는 optimal substructure를 갖는 것처럼 보이지 않는다. 이 문제에 대한 어떠한 효율적인 dynamic-programming algorithm이 발견되지 않았따. 사실, 이 문제는 NP-complete이고, - 우리가 Chapter 34에서 보게 되듯이 - 그것은 우리가 polynomial time에 그것을 해결 할 방법을 찾을 수 없다는 것을 의미한다.

longest simple path의 substructure는 shortest path의 그것와 매우 다른 이유가 무엇인가? longest and shortest paths 둘 다 한 문제에 대한 solution이 두 개의 subproblems를 사용하지만, longest simple path를 찾을 떄의 subproblems은 independent하지 않다. 반면에, shortest paths에 대해, 그것들은 그렇다. subproblems이 독립적이라는 말은 무엇을 의미하는가? 한 subproblem에 대한 solution이 같은 문제의 또 다른 subproblem의 solution에 영향을 미치지 않는 다는 것을 의미한다. 그림 15.6의 예시에 대해, 우리는 두 개의 subproblems을 가진 $q$에서 $t$로 가는 longest simple path를 찾는 문제를 가진다: $q$에서 $r$로 가는 것과 $r$에서 $t$로 가는 longests simple path를 발견하는 것. 이러한 subproblems의 첫번쨰 것에 대해, 우리는 그 경로 $q \rightarrow s \rightarrow t \rightarrow r$를 선택하고, 그래서 우리는 또한 정점 $s$와 $t$를 가진다. 우리는 더 이상 두 번째 subproblem에서 이러한 정점들을 사용할 수 없다. 왜냐하면 subproblems에 대한 두 solutions의 조합은 simple하지 않은 path를 만들것이기 때문이다. 만약 우리가 second problemdㅔ서 vertex $t$를 쓸 수 없다면, 그러면 우리는 그것을 전혀 해결할 수 없다. 왜냐하면 $t$는 우리가 찾는 경로에서 있기를 요구되어지기 떄문이고, 그것은 그 subproblem solutions을 "splicing(잇는)"하는 정점이 아니기 때문이다. 우리는 한 subproblem solutions에서 정점들 $s$와 $t$를 사용하기 떄문에, 우리는 다른 subproblem solution에서 그것들을 사용할 수 없다. 우리는 다른 subproblem을 해결하기 위해 적어도 그것들 중 하나를 사용해야 한다. 그러나, 우리는 그것을 optimally하게 해결하기 위해 그것들 둘 다 사용해야 한다. 따라서, 우리는 이러한 subproblems이 독립적이지 않다고 말한다. 또 다른 방식으로 보아도, 한 subproblem를 해결할 때의 resources를 사용하는 것 (그러한 resources는 vertices이다)은 다른 subproblem에 대해 이용가능하지 않게 만든다.

그러면 shortest path를 찾는데 있어서 그 subproblems은 왜 독립적인가? 그 답은 본질 상, 그 subproblems은 resources를 공유하지 않는다는 것이다. 우리는 만약 한 정점 $w$가 $u$에서 $v$로 가는 최단 경로 $p$에 있다면, 그러면 우리는 어떤 최단 경로 $u \leadsto^{p_1} w$와 어떤 최단 경로 $w \leadsto^{p_2} v$를 이을 수 있다, $u$에서 $v$로 가는 최단 경로를 만들기 위해서. $w$외에, 어떠한 정점이 두 경로 $p_1$과 $p_2$에 나타나지 않는다는 것이 보장된다. 왜 그런가? 어떤 정점 $x \neq w$이 $p_1$과 $p_2$에 나타난다고 가정해보자, 우리는 $p_1$를 $u \leadsto^{p_{ux}} x \leadsto w$로 분해할 수 있고, $p_2$를 $w \leadsto x \leadsto^{p_{xv}} v$로 분해할 수 있다. 이 문제의 optimal substructure에 의해, 경로 $p$는 $p_1$과 $p_2$만큼의 edges를 가진다; $p$가 $e$ edges를 가진다고 해보자. 이제 우리가 $u$에서 $v$로 가는 경로 $p' = u \leadsto^{p_{ux}} x \leadsto^{p_{xv}} v$를 구성해보자. 우리는 $x$에서 $w$로 가는 경로를 자르고, $w$에서 $x$로 가는 경로를 자르기 때문에, 그 경로 각각은 적어도 한 개의 edge를 포함하고, 경로 $p'$는 최대 $e - 2$ edges를 포함한다. 그리고 이것은 $p$가 shortest path라는 가정을 반박한다. 따라서, shortest-path problem에 대한 subproblems이 독립적이라고 보장된다.

Section 15.1과 15.2에서 조사된 두 문제들은 독립적인 subproblems을 가진다. matrix-chain multiplication에서, 그 subproblems은 subchains $A_i{A_{i+1} \cdots A_k}$와 $A_{k+1} A_{k+2} \cdots A_j$를 곱하는 것이다. 이러한 subchains은 분리되어 있고, 어떠한 matrix가 가급적 그 둘 다에 포함될 수 없게 된다. rod cutting에서, 길이가 n인 막대를 자르는 가장 좋은 방법을 결정하기 위해, 우리는 $i = 0, 1, \dots, n - 1$에 대해 길이가 $i$인 막대들을 자르는 최고의 방법들을 본다. 길이가 n인 문제에 대한 optimal solution은 이러한 subproblem solutions중의 하나를 포함하기 떄문에 (우리가 그 첫 번째 조각을 자른 후에), subproblems의 독립성은 문제가 되지 않는다.

Overlapping subproblems

optimization problem이 dynamic programming을 적용하기 위해 가져야 하는 두 번째 재료는 항상 새로운 subproblems을 생성하는 것이 아니라 subproblems의 space가 문제에 대한 재귀 알고리즘이 그 같은 subproblems을 반복해서 해결하는 의미에서 "small"해야 한다는 것이다. 일반적으로 별개의 subproblems의 총 개수는 input size에서 polynomial하다. 재귀 알고리즘이 그 같은 문제를 반복적으로 재방문 할 때, 우리는 optimization problem이 overlapping subproblems²를 가진다고 말한다. 대조적으로 divide-and-conquer approach이 적합한 문제는 보통 재귀의 매 단계에서 새로운 문제들을 생성한다. Dynamic-programming algorithms은 일반적으로 각 subproblem을 한 번만 해결하고, 그러고나서 필요할 때 look up될 수 있는, lookup 당 constant time을 사용하여, 테이블에 solution을 저장하여 overlapping subproblems을 이용한다.

Section 15.1에서, 우리는 간다히 rod cutting에 대한 재귀 솔루션이 더 작은 subproblems의 solutions을 찾는데 exponentially하게 많은 호출을 만들어내는 것을 조사했었다. 우리의 dynamic-programming solution은 exponential-time recursive algorithm을 quadratic time으로 만든다.

좀 더 상세하게 overlapping-subproblems property를 보여주기 위해, matrix-chain multiplication problem을 조사해보자. 그림 15.5를 참고하여, MAXTRIX-CHAIN-ORDER가 더 높은 행에 있는 subproblems를 해결할 때, 더 낮ㅈ은 행에 있는 subproblems에 대한 해결책을 반복적으로 looks up하는 것을 관찰해보자. 예를들어, 그것은 entry $m[3,4]$를 네 번 참조한다: $m[2,4], m[1,4], m[3,5], m[3,6]$의 연산 동안.

 

---

 

만약 우리가 매번 $m[3,4]$를 재연산하려고 한다면, 그것을 look up하기 보다는, 그 작동 시간은 극적으로 증가할 것이다. 어떻게 그런지를 보기 위해, 다음의 (비효율적인) 재귀 함수를 봐보자. 이것은 $m[i,j]$를 결정하는데, matrix-chain product $A_{i..j} = A_i A_{i+1} \cdots A_j$를 연산하는데 필요한 최소한의 scalar multiplications이다. 그 procedure는 직접적으로 반복 (15.7)를 기반으로 한다.

xxxxxxxxxx
RECURSIVE-MATRIX-CHAIN(p,i,j)
1   if i == j
2       return 0
3   m[i,j] = infinity
4   for k = i to j - 1
5       q = RECURSIVE-MATRIX-CHAIN(p,i,k)
            + RECURSIVE-MATRIX-CHAIN(p, k+1, j)
            + p_i-1 p_k p_j
6       if q < m[i,j]
7           m[i,j] = q
8   return m[i,j]

그림 15.7은 RECURSIVE-MATRIX-CHAIN(p,1,4)로 만들어진 재귀 트리를 보여준다. 각 노드는 parameters i와 j의 값으로 라벨이 붙는다. values의 어떤 쌍들은 여러 번 발생하는 것을 관찰해라.

사실, 이 재귀 procedure에 의해 $m[1,n]$를 연산하는 시간은 n에 적어도 exponential하다는 것을 보여줄 수 있다. n개의 행렬의 chain의 optimal parenthesization을 연산하는 RECURSIVE-MATRIX-CHAIN에 의해 걸리는 시간을 $T(n)$으로 표기하자. lines 1-2와 6-7의 실행은 적어도 단위 시간이 걸리는데, line 5에서 곱셈이 그렇듯이, 그 proceudre의 검사는 다음의 반복을 만들어 낸다.

$$\begin{split} & T(1) \geq 1 \\ & T(n) \geq 1 + \sum^{n-1}_{k=1} (T(k) + T(n - k) + 1) \;\;\; \text{for n > 1.} \end{split}$$

$i = 1, 2, \dots, n - 1$에 대해, 각 항 $T(i)$는 $T(k)$로서 한 번 나타나고, $T(n-k)$로서 한 번 나타나는 것에 주목하고, 그 $n - 1$개의 1를 합에서 모아서, 우리는 그 반복을 다음으로 다시 작성할 수 있다

$$T(n) \geq 2 \sum^{n-1}_{i=1} T(i) + n. \;\;\;\; (15.8)$$

우리는 $T(n) = \Omega(2^n)$라는 것을 치환 방법으로 증명할 것이다. 구체적으로 우리는 모든 $n \geq 1$에 대해 $T(n) \geq 2^{n-1}$ 라는 것을 보여줄 것이다. 그 기저는 쉽다, 왜냐하면 $T(1) \geq 1 = 2^0$이기 떄문이다. 귀납적으로, $n \geq 2$에 대해, 우리는 다음을 갖는다

$$\begin{split} T(n) & \geq 2 \sum^{n-1}_{i=1} 2^{i-1} + n \\ & = 2 \sum^{n-2}_{i = 0} 2^i + n \\ & = 2(2^{n-1} - 1) + n \;\; \text{by equation(A.5)} \\ & = 2^n - 2 + n \\ & \geq 2^{n-1} \end{split}$$

이것은 그 증명을 완성짓는다. 따라서, 그 호출 RECURSIVE-MATRIX-CHAIN(p,1,n)에 의해 수행되는 작업의 양은 적어도 n에 exponential 하다.

(memoization없는)이 top-down, recursive algorithm을 bottom-up dynamic-programming과 비교해라. 그 후자는 좀 더 효율적인데, overlapping-subproblems property를 이용하기 때문이다. Matrix-chain multiplication은 $\Theta(n^2)$의 별개의 subproblems만을 가지고, 그 dynamic-programming은 각각을 정확히 한 번만 해결한다. 반면에, 그 재귀 알고리즘은 그것이 재귀 트리에서 다시 나타날 때 마다 각 subproblem을 다시 해결해야 한다. 한 문제에 대한 natural recursive solution을 위한 recursion tree가 같은 subproblem을 반복적으로 포함할 때 마다, 그리고 그 별개의 subproblems의 총 개수가 작을 때 마다, dynamic programming은 효율성을, 가끔씩은 극적으로, 개선할 수 있다.

Reconstructing an optimal solution

실용적인 문제로서, 우리가 저장했었던 이 정보를 그 비용으로부터 재구성할 필요 없게 하기 위해, 한 테이블에 각 subproblem에서 우리가 했던 선택을 저장한다.

matrix-chain multiplication에 대해, 그 table $s[i,j]$는 optimal solution을 재구성할 때 드는 많은 양의 작업을 절ㄹ약시켜준다. 우리가 $s[i,j]$ table를 유지하지 않는다고 가정해보자, 그리고 optimal subproblem costs를 포함하는 table $m[i,j]$에만 채운다. 우리는 $A_iA_{i+1} \cdots A_j$를 parenthesizing하는 것에 대한 optimal solution에서 사용할 어떤 subproblems를 결정할 때, $j - i$개의 가능성 중에서 선택하고, $j - i$는 상수가 아니다. 그러므로, 그것은 주어진 문제에 대한 solution에 대해 우리가 어떤 subproblems을 선택했는지를 재구성하는데 $\Theta(j - i ) = \omega(1)$의 시간이 걸릴 것이다. $s[i,j]$에 우리가 곱 $A_i A_{i+1} \cdots A-j$를 분리한 matrix의 index를 저장하여, 우리는 $O(1)$ time에 각 선택을 재구성할 수 있다.

Memoization

우리가 rod-cutting problem에 대해 보았듯이, top-down strategy를 유지하면서, bottom-up dynamic programming의 효율성을 종종 제공하는 dynamic programming에 대한 대안의 접근법이 있다. 그 아이디어는 natural하지만, 비효율적인 recursive algorithm을 memoize하는 것이다. bottom-up approach에서 그랫듯이, 우리는 subproblem solutions을 가진 table를 유지하지만, 그 table를 채우기 위한 제어 구조는 재귀 알고리즘과 더 비슷하다.

memoized recursive algorithm은 각 subproblem에 대한 solution를 위해 한 table에 entry를 유지한다. 각 table entry는 초기에 그 entry가 아직 채워져야 한다는 것을 가리키는 특별한 값을 포함한다. 그 subproblem이 처음에 만나졌을 때, 그 recursive algorithm이 펼쳐질 때, 그것의 solution이 연산되고 그러고나서 그 table에 저장된다. 우리가 이 subproblem을 만나는 각 이후의 때 마다, 우리는 간단히 그 테이블에 저장된 값을 look up하고, 그것을 반환한다 ³.

여기에 RECURSIVE-MATRIX-CHAIN의 memoized version이 있다. 그것이 어디에서 rod-cutting problem에 대해 memoized top-down method와 닮은지를 유의해라.

 

---

 

​x
MEMOIZED-MATRIX-CHAIN(p)
1   n = p.length - 1
2   let m[1..n, 1..n] be a new table
3   for i = 1 to n
4       for j = i to n
5           m[i, j] = infinity
6   return LOOKUP-CHAIN(m,p,1,n)
​
LOOKUP-CHAIN(m,p,i,j)
1   if m[i,j] < infinity
2       return m[i,j]
3   if i == j
4       m[i,j] = 0
5   else for k = i to j - 1
6           q = LOOKUP-CHAIN(m,p,i,k) 
                + LOOKUP-CHAIN(m,p,k+1,j) + p_{i-1}p_kp_j
7           if q < m[i,j]
8               m[i,j] = q
9   return m[i,j]

그MATRIX-CHAIN-ORDER처럼, 그 MEMOIZED-MATRIX-CHAIN procedure는 행렬 $A_{i..j}$를 연산하는데 필요한 scalar multiplications의 최소개수인 $m[i,j]$의 연산된 값의 table $m[1..n,1..n]$를 유지한다. 각 table entry는 처음에 그 entry가 아직 채워져야 한다는 것을 가리키기 위해 $\infty$의 값을 포함한다. LOOKUP-CHAIN(m,p,i,j)를 부를 때 마다, 만약 line 1이 $m[i,j] < \infty$를 인것을 발견하면, 그러면 그 procedure는 간단히 그 이전에 연산된 cost $m[i,j]$를 line2에서 반환한다. 만약 그렇지 않다면, 그 비용은 RECURSIVE-MATRIX-CHAIN에서 연산되고, $m[i,j]$에서 저장되어지고, 그리고 반환된다. 따라서, LOOKUP-CHAIN(m, p, i, j)는 항상 $m[i,j]$의 값을 반환하지만, 그것은 이러한 특정한 값의 $i$와 $j$로 LOOKUP-CHAIN의 첫 번째 호출신에 그것을 연산한다.

그림 15.7은 MEMOIZED-MATRIX-CHAIN이 RECURSIVE-MATRIX-CHAIN과 비교하여 시간을 어떻게 절약하는지를 보여준다. 색칠된 subtrees는 재연산되기보다는 looks up하는 값들을 나타낸다.

bottom-up dynamic-programming algorithm의 MATRIX-CHAIN-ORDER처럼, 그 procedure MEMOIZED-MATRIX-CHAIN은 $O(n^3)$ 시간에 작동한다. MEMOIZED-MATRIX-CHAIN의 line 5는 $\Theta(n^2)$ times에 작동한다. 우리는 LOOKUP-CHAIN의 호출을 두 유형으로 분류할 수 있다:

1. $m[i,j] = \infty$인 호출들, lines 3-9가 실행되고,
2. $m[i,j] < \infty$인 호출들, line 2에서 LOOKUP-CHAIN이 간단히 반환된다.

table entry마다 하나씩 첫 번째 type의 $\Theta(n^2)$ calls이 있다. second type의 모든 calls은 그 첫 번째 type의 calls에 의한 recursive calls로서 만들어진다. LOOKUP-CHAIN의 주어진 call이 recursive calls를 만들 때 마다, 그것은 그것들의 $O(n)$를 만든다. 그러므로, 모든 것에서 second type의 $O(n^3)$ calls이 있다. second type의 각 호출은 $O(1)$ time이 걸리고, 그 첫 번째 type의 각 호출은 $O(n)$ time과 그것의 재귀 호출에서 쓰이는 시간이 더해진다. 그러므로 총 시간은 $O(n^3)$이다. 따라서 Memoization은 $\Omega(2^n)$-time algorithm을 $O(n^3)$-time algorithm을 바꾼다.

요약하여, 우리는 top-down, memoized dynamic-programming algorithm이든 bottom-up dynamic programming algorithm이든 둘 중 하나로 $O(n^3)$ time에 matrix-chain multiplication problem을 풀 수 있다. 두 방법들은 overlapping-subproblems property를 이용한다. 총 오직 $\Theta(n^2)$의 별개의 subproblems이 있고, 이러한 방법 들 중 하나는 각 subproblem에 대한 solution을 오직 한 번만 연산한다. memoization 없이, natural recursive algorithm은 exponential time에서 작동하는데, sovled subproblems이 반복적으로 해결되어야 하기 때문이다.

일반적인 예시에서, 만약 모든 subproblems이 적어도 한 번 해결되어야 한다면, bottom-up dynamic-programming algorithm이 보통 대응되는 top-down memoized algorithm을 상수 요소만큼 더 잘 수행한다. 왜냐하면 그 bottom-up algorithm은 recursion에 overhead가 없고, 그 table를 유지하는데 overhead가 덜 들기 때문이다. 게다가, 어떤 문제에 대해, 우리는 time or space requirements를 더욱 줄이기 위해 dynamic programming algorithm에서 table accesses의 regular pattern을 이용한다. 대안적으로, 만약 subproblem spcae에서 어떤 subproblems들이 전혀 해결될 필요가 없다면, memoized solution은 명확히 요구되는 subproblems들만 푸는 것의 이점을 가진다.

 

15.4 Longest common subsequence

Biological applications은 종종 다른 두 개 이상의 유기체의 DNA를 비교할 필요가 있다. DNA의 한 실은 bases라고 불려지는 molecules의 한 string으로 구성되어 있다. 거기에서 가능한 bases는 adenine, guanine, cytosine, and thmine이다. 이러한 bases 각각을 그것의 initial letter로 나타내어, 우리는 DNA의 한 strand를 유한한 집합 ${A, C, G, T}$에 대해 한 string으로서 표현할 수 있다. (string에 대한 정의를 위해 Appendix C를 보아라.) 예를들어, 한 유기체의 DNA는 $S_1 = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA$ 이고, 또 다른 유기체의 DNA는 $S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA.$ 일지도 모른다. DNA의 두 strands를 비교하는 한 가지 이유는 two strands가 얼마나 유사한지를 결정하기 위해서인데, 그 두 유기체가 얼마나 가까운지에 대한 척도가 된다. 우리는 많은 다른 방법들로 유사성을 정의할 수 있고 그렇게 한다. 예를들어, 우리는 만약 하나가 다른 것의 substring이라면 두 개의 DNA strands가 비슷하다고 말할 수 있다. (Chapter 32는 이 문제를 해결하는 알고리즘을 조사한다.) 우리의 예제에서, $S_1$과 $S_2$ 둘 다 다른 것의 substring이 아니다. 대안적으로, 우리는 만약 하나를 다른 것으로 바꾸는데 필요한 변화의 개수가 적다면 두 strands가 비슷하다고 말할 수 있다. (Problem 15-5가 이 개념을 본다.) 그러나, strands $S_1$과 $S_2$의 유사성을 측정하는 또 다른 방법은 세 번째 strand인 $S_3$를 찾는 것인데, $S_3$의 bases는 $S_1$과 $S_2$의 각각에서 나타난다; 이러한 bases는 같은 순서로 나타나야 하지만, 반드시 연속한 것은 아니다. 우리가 찾는 strand $S_3$ 길면 더 길 수록, $S_1$과 $S_2$의 더 유사하다. 우리의 예제에서, 그 longest strand $S_3$은 $GTCGTCGGAAGCCGGCCGAA.$

우리는 유사성의 이 마지막 개념을 longest-common-subsequence 문제라고 공식화한다. 주어진 sequence의 subsequence는 zero 또는 좀 더 많은 elements가 제거된 주어진 sequence이다. 공식적으로, 한 sequence $X = \langle x_1, x_2, \dots, x_m \rangle$가 주어진다면, 또 다른 sequence $Z = \langle z_1, z_2, \dots, z_k \rangle$은 X의 subsequence인데, 만약 모든 $j = 1, 2, \dots , k$에 대해 우리가 $X_{i_j} = z_j$를 가지도록 하는 $X$의 indices의 엄격하게 증가하는 sequence인 $\langle i_1, i_2, \dots, i_k \rangle$가 존재한다면. 예를들어, $Z = \langle B, C, D, B \rangle$은 $X = \langle A, B, C, B, D, A, B \rangle$의 subsequence인데, 대응되는 index sequence $\langle 2, 3, 5, 7 \rangle$를 가진다.

두 개의 sequences $X$와 $Y$가 주어진다면, 우리는 만약 $Z$가 $X$와 $Y$ 둘 다에 대한 subsequence라면, $X$와 $Y$의 common subsequence라고 말한다. 예를들어, 만약 $X = \langle A, B, C, B, D, A, B \rangle$ 이고 $Y = \langle B, D,C,A,B,A \rangle$라면, 그 sequence $\langle B, C, A \rangle$는 $X$와 $Y$ 둘 다에 대한 common subsequence이다. 그러나, 그 sequence $\langle B, C, A \rangle$은 X와 Y의 longest common subsequence (LCS)가 아니다. 왜냐하면 그것은 길이 3를 갖는데, sequence $\langle B,C,B,A \rangle$는 또한 X와 Y에 대해 공통인데, 길이 4를 갖기 때문이다. 그 sequence는 $\langle B, C, B, A \rangle$는는 X와 Y의 LCS이다, $\langle B, D, A, B \rangle$가 그렇듯이, 왜냐하면 X와 Y는 길이가 5보다 더 큰 common subsequence를 갖고있지 않기 때문이다.

longest-common-subsequence problem에서, 우리는 두 개의 sequences $X = \langle x_1, x_2, \dots, x_m \rangle$과 $Y = \langle y_1, y_2, \dots, y_n \rangle$가 주어지고, X와 Y의 maximum-length의 common subsequence를 찾기를 원한다. 이 섹션은 dynamic programming을 사용하여 그 LCS 문제를 어떻게 효율적으로 해결하는지를 보여준다.

 

Step 1 : Characterizing a longest common subsequence

LCS problem을 해결하는데 있어서 brute-force 전략에서, 우리는 X의 모든 subsequence를 열거하고, 그것이 또한 Y의 subsequence인지를 보기위해 각 subsequencㄷ를 체크하고, 우리가 발견한 가장 긴 subsequence를 추적한다. X의 각 subsequence는 X의 인덱스들 $\{1,2, \dots m\}$의 한 subset과 동일하다. X는 $2^m$의 subsequence를 가지기 때문에, 이 전략은 exponential time을 요구하고, long sequences에 대해 비실용적이다.

LCS problem은 그러나 optimal-substructure property를 가지고 있는데, 다음의 정리가 보여준다. 우리가 보게 되듯이, subprobems의 natural classes는 두 개의 input sequences의 "prefixes"의 쌍과 대응된다. 정확히 해서, 한 sequence $X = \langle x_1, x_2 \dots, x_m \rangle$가 주어진다면, 우리는 X의 i번째 prefix를 정의한다, $i = 0, 1, \dots, m$에 대해, $X_i = \langle x_1, x_2 \dots, x_i\rangle$로서. 예를들어, 만약 $X = \langle A, B,C,B,D,A,B \rangle$라면, $X_4 = \langle A,B,C,B \rangle$이고, $X_0$은 empty sequence이다.

 

Theorem 15.1 (Optimal substructure of an LCS)

$X = \langle x_1, x_2 \dots, x_m \rangle$과 $Y = \langle y_1, y_2, \dots, y_n \rangle$이 sequences라고 하고, $Z = \langle z_1,z_2,\dots, z_k\rangle$가 X와 Y의 어떤 LCS라고 하자.

1. 만약 $x_m = y_n$이면, 그러면 $z_k = x_m = y_n$이고, $Z_{k-1}$은 $X_{m-1}$과 $Y_{n-1}$의 LCS이다.
2. 만약 $x_m \neq y_n$이라면, 그러면 $z_k \neq x_m$은 Z가 $X_{m-1}$과 $Y$의 LCS라는 것을 암시한다.
3. 만약 $x_m \neq y_n$라면, 그러면 $z_k \neq y_n$은 Z가 X와 $Y_{n-1}$의 LCS라는 것을 암시한다.

Proof (1) 만약 $z_k \neq x_m$이라면, 그러면 우리는 길이가 $k + 1$인 X와 Y의 common subsequence를 얻기위해 Z에 $x_m = y_n$을 더할 수 있고, 이것은 Z가 X와 Y의 longest common subsequence라는 가정과 모순이 된다. 따라서, 우리는 $z_k = x_m =y_n$을 가져야만 한다. 이제, 그 prefix $Z_{k-1}$은 $X_{m-1}$과 $Y_{n-1}$의 길이가 $(k-1)$인 common subsequence이다. 우리는 그것이 LCS라는 것을 보여주고 싶다. $k - 1$보다 더 큰 길이를 가진 $X_{m-1}$과 $Y_{n-1}$의 common subsequence $W$가 존재한다고 모순의 목적으로 가정해보자. 그러고나서, W에 $x_m = y_n$를 추가하는 것은 k보다 더 긴 X와 Y의 common subsequence를 만들어내고, 이것은 모순이다.

(2) 만약 $z_k \neq x_m$이라면, 그러면 Z는 $X_{m-1}$과 $Y$의 common subsequence이다. 만약 $X_{m-1}$과 $Y$의 k보다 더 긴 길이의 common subsequence가 있다면, 그러면 W는 $X_m$과 $Y$의 common subsequence가 또한 될 것이다. 그리고 이것은 Z가 X와 Y의 LCS라는 가정과 모순이 된다.

(3) 그 증명은 (2)와 대칭이다.

 

Theorem 15.1이 longest common subsequences를 특징화하는 방식은 우리에게 sequences의 한 LCS는 그것 내에서 두 sequences의 prefixes중의 하나를 포함한다는 것을 말한다. 따라서, 그 LCS problem은 한 optimal-substructure property를 가진다. 또한 한 recursiv esolution은 우리가 보게될 overlapping-subproblems property를 ㅏㄱ진다.

 

Step 2: A recursive solution

Thoeorem 15.1은 우리가 $X = \langle x_1, x_2 \dots, x_m \rangle$과 $Y = \langle y_1, y_2, \dots, y_n \rangle$의 한 LCS를 찾을 때, 하나 또는 두 subproblems중 하나를 조사해야 한다는 것을 암시한다. 만약 $x_m = y_n$이라면, 우리는 $X_{m-1}$과 $Y_{n-1}$의 LCS를 찾아야 한다. 이 LCS에 $x_m = y_n$ 추가하여 X와 Y의 LCS를 만들어 낸다. 만약 $x_m \neq y_n$이라면, 그러면 우리는 두 개의 subproblems를 풀어야 한다 : $X_{m-1}$과 $Y$의 LCS를 찾고, $X$와 $Y_{n-1}$의 찾는 것. 이러한 두 LCS 중에 더 긴 것이 X와 Y의 LCS이다. 이러한 cases들이 모든 가능성을 사용하기 때문에, 우리는 optimal subproblem중 하나가 X와 Y의 LCS내에서 나타나야 한다느 ㄴ것을 안다.

우리는 쉽게 LCS problem에서 overlapping-subproblems property를 볼 수 있다. X와 Y의 LCS를 찾기 위해, 우리는 $X$와 $Y_{n-1}$의 LCSs 그리고 $X_{m-1}$과 $Y$의 LCs를 찾을 필요가 있다. 그러나 이러한 subproblems의 각각은 $X_{m-1}$과 $Y_{n-1}$의 LCS를 찾는 subsubproblem을 가진다. 많은 다른 subproblems은 subsubproblems을 공유한다.

matrix-chain multiplication problem에서도 그렇듯이, LCS 문제에 대한 우리의 recursive solution은 optimal solution의 값에 대한 재귀를 구축하는 것을 포함한다. $X_i$와 $Y_j$의 sequences의 LCS의 길이가 $c[i,j]$라고 하자. 만약 $i = 0$이거나 $j = 0$ 둘 중 하나라면, 그 sequences중의 하나는 길이 0을 갖고, 그래서 그 LCS는 길이 0을 가진다. LCS problem의 optimal substructure는 다음의 재귀 공식을 준다

$$c[i,j] = \bigg\{ \begin{split} & 0 \;\;\;\;\;\;\; \text{if } i = 0 \text{ or } j = 0 \\ & c[i - 1, j - 1] + 1 \;\;\;\;\;\;\; \text{if } i, j > 0 \text{ and } x_i = y_j \\ & max(c[i, j-1], c[i-1, j]) \;\;\;\;\;\;\; \text{if } i, j > 0 \text{ and } x_i \neq y_j \end{split} \\ (15.9)$$

이 재귀 공식에서, 문제에 있는 조건이 우리가 고려한 subproblems을 제한한다는 것을 관찰해라. $x_i = y_i$일 때, 우리는 $X_{i-1}$과 $Y_{j-1}$의 LCS를 발견하는 subproblem을 고려해야 한다. 만약 그렇지 않다면, 우리는 $X_i$와 $Y_{j-1}$ 그리고 $X_{i-1}$과 $Y_j$의 LCS를 찾는 두 subproblems을 고려한다. 이전 우리가 알아본 dynamic-programming algorithms에서- rod cutting과 matrix-chain multiplication - 우리는 문제에서의 conditions에 의한 subproblems을 제외하지 않았다. LCS를 찾는 것은 문제에서 conditions에 기반하여 subproblems을 배제하는 유일한 dynamic-programming algorithm은 아니다. 예를들어, edit-distance problem은 이 특징을 갖는다 (Problem 15-5를 보아라).

 

Step 3 : Computing the length of an LCS

방정식 (15.9)를 기반으로, 우리는 쉽게 두 sequences의 LCS의 길이를 연산하는 exponential-time recursive algorithm을 작성할 수 있다. 그 LCS problem은 오직 $\Theta(mn)$의 별개의 subproblems을 가지기 떄문에, 그러나, 우리는 그 solutions을 bottom up으로 연산하기 위해 dynamic programming을 사용할 수 있다.

Procedure LCS-LENGTH는 두 개의 $X = \langle x_1, x_2 \dots, x_m \rangle$과 $Y = \langle y_1, y_2, \dots, y_n \rangle$를 입력으로 받는다. 그것은 한 TABLE $c[0..m, 0..n]$의 table에서 $c[i,j]$ values를 저장하고, row-major order로 그 entires를 연산한다. (즉, 그 procedures는 c의 first row를 왼쪽에서 오른쪽으로 채워가고, 그러고나서 두 번째 row에 등등.) 그 procedure는 또한 우리가 optimal solution을 구성하게 도와줄 tabl e $b[1..m,1..n]$를 유지한다. 직관적으로, $b[i,j]$는 $c[i,j]$를 연산할 때, 선택된 optimal subproblem solution에 대응되는 table entry를 가리킨다. 그 procedure는 b와 c tables를 반환한다; $c[m,n]$은 X와 Y의 LCS 길이를 포함한다.

xxxxxxxxxx
LCS-LENGHT(X,Y)
1   m = X.length
2   n = Y.length
3   let b[1..m, 1..n] and c[0..m, 0..n] be new tables
4   for i = 1 to m
5       c[i, 0] = 0
6   for j = 0 to n
7       c[0, j] = 0
8   for i = 1 to m
9       for j = 1 to n
10      if x_i == y_j
11          c[i, j] = c[i - 1, j - 1] + 1
12          b[i, j] = "NW"
13      elseif c[i - 1, j] >= c[i, j - 1]
14          c[i, j] = c[i - 1, j]
15          b[i, j] = "N"
16      elsec[i, j] = c[i, j -1]
17          b[i, j] = "W"
18  return c and b

그림 15.8은 sequences $X = \langle A, B,C,B,D,A,B \rangle$과 $Y = \langle B,D,C,A,B,A \rangle$에 대한 LCS-LENGTH로 만들어진 테이블을 보여준다. 그 procedure의 running time은 $\Theta(mn)$인데, 각 table entry는 연산하는데 $\Theta(1)$ time이 걸리기 때문이다.

 

Step 4 : Constructing an LCS

LCS-LENGTH에 반환되는 b table은 우리가 $X = \langle x_1, x_2 \dots, x_m \rangle$과 $Y = \langle y_1, y_2, \dots, y_n \rangle$의 LCS를 빠르게 구성하게 해준다. 우리는 간단히 b[m,n]에서 시작하여 그리고 그 화살표를 따라가서 테이블을 통해 추적한다. 우리가 entry $b[i,j]$에서 "NW"를 만날 때 마다, 그것은 $x_i = y_j$가 LCS-LENGTH가 발견한 LCS의 한 element라는 것을 암시한다. 이 방법으로, 우리는역순으로 이 LCS의 elements를 만난다. 다음의 재귀 procedure는 적절한 순서대로 X와 Y의 LCS를 출력한다. 그 initial call은 PRINT-LCS(b, X, X.length, Y.length)이다.

xxxxxxxxxx
PRINT-LCS(b,X,i,j)
1   if i == 0 or j ==0
2       return
3   if b[i,j] == "NW"
4       PRINT-LCS(b, X, i - 1, j - 1)
5       print x_i
6   elseif b[i,j] == "N"
7       PRINT-LCS(b, X, i - 1, j)
8   elsePRINT-LCS(b, X, i, j - 1)

그림 15.8에 있는 b table에 대해, 이 procedures는 BCBA를 출력한다. 그 procedure는 $O(m+n)$의 시간이 걸리는데, 그것이 각 recursive call에서 i와 j의 적어도 한 개씩 줄어들기 때문이다.

 

Improving the code

너가 한 알고리즘을 개발했다면, 너는 종종 그것이 사용하는 공간이나 시간에서 개선할 수 있다는 것을 발견할 것이다. 어떤 변화들은 그 코드를 간단하게 하고, 상수 요소를 개선하지만, 만약 그렇지 않다면 성능에서 어떠한 asymptotic improvement를 만들지 않는다. 다른것들은 time and space에서 상당한 asymptotic savings을 만들어낼 수 있다.

LCS algorithm에서, 예를들어, 우리는 전적으로 b table를 제거할 수 있다. 각 $c[i,j]$ entry는 오직 세 개의 다른 c table entries만을 의존한다: $c[i-1,j-1], c[i-1,j], c[i,j-1]$. $c[i,j]$의 값이 주어진다면, 우린느 이러한 세 개의 값들 중 어떠한 것이 $c[i,j]$를 연산하는데 사용되었는지를 $O(1)$ time에 결정할 수 있다, table b를 보지 않고. 따라서, 우리는 PRINT-LCS와 유사한 procedure를 사용하여 $O(m+n)$ time에 LCS를 재구성할 수 있다 (Exercise 15.4-2가 그 슈됴코드를 주라고 너에게 요청한다.) 비록 우리가 이 방식으로 $\Theta(mn)$ space를 절약할지라도, LCS를 연산하기 위한 그 보조 space requirement는 asymptoticall하게 감소하지 않는데, 우리는 c table에 대해 어쨋든 $\Theta(mn)$ space가 필요하기 때문이다.

그러나, 우리는 LCS-LENGTH에 대해 asymptotic space requirements를 줄일 수 있는데, 그것이 한 번에 table의 오직 두 개의 rows만을 필요하기 때문이다: 계산되고 있는 row와 이전 row. (사실, Exercise 15.4-4가 너에게 이것을 보이라고 요청하듯이, 우린느 LCS의 length를 연산하기 위해 c의 한 행에 대한 space보다 조금 더 많은 것만 사용할 수 있다.) 이 개선은 만약 우리가 LCS의 길이만 필요하다면 효과가 있다; 만약 우리가 LCS의 elements를 다시 구성할 필요가 있다면, 그 더작 table은 $O(m+n)$ time에 우리의 steps을 추적하는데 충분한 정보를 유지하지 못한다.

 

15.5 Optimal binary search trees

우리가 영어에서 프랑스어로 글을 번역하는 프로그램을 설계한다고 가정하자. 글에서 각 영어 단어가 나타나는 것에 대해, 우리는 그것의 프랑스어와 같은 것을 찾아볼 필요가 있다. 우리는 n개의 English words를 keys로 하고, 그것들의 French equivalents를 satellite data로서 가진 이진 탐색 트리를 만들어서 이러한 lookup 연산을 수행할 수 있다. 그 글에서 각 개별 단어를 위한 tree를 탐색할 것이기 때문에, 우리는 탐색하는데 소비되는 총 시간을 가능한 낮게 하고 싶어한다. 우리는 red-black tree 또는 어떤 다른 balanced binary search tree를 사용하여 나타나는 것 마다의 $O(lg\;n)$ search time을 보장할 수 있다. 그러나, 단어들은 다른 빈도를 가진 채 나타나고, 그래서 the 같은 자주 사용되는 단어는 root에서 멀리에 나타날지도 모른다, 반면에 거의 사용되지 않은 단어인 machicolation이 root 근처에 나타날 수 있다. 그러한 구성은 번역을 느리게 할 것인데, 왜냐하면 binary search tree에서 한 key를 탐색할때 방문되는 노드의 개수가 그 키를 구성하는 노드의 depth + 1를 한 것과같기 때문이다. 우리는 글에서 자주 나타나는 단어들이 root에 더 가깝게 위치하도록 하고 싶다. 게다가, 그 글에서 어떤 단어들은 어떠한 프랑스어 번역을 가지지 않을지도 모른다. 그래서 그러한 단어들은 binary search tree에전혀 없을지도 모른다. 우리가 각 단어가 얼마나 종종 나타나는 지를 안다고 하면, 모든 탐색에서 방문되는 노드들의 개수를 최소화 하기 위해 binary search tree를 어떻게 구성하는가?

우리가 필요한 것은 optimal binary search tree이다. Formally하게, 우리는 정렬된 순서로 ($k_1 < k_2 < \cdots < k_n$이 되도록 하는) n개의 별개의 keys의 한 sequence $K = \langle k_1, k_2, \dots, k_n \rangle$가 주어진다. 그리고 우리는 이러한 keys들로부터 한 binary search tree를 구성하고 싶다. 각 key $k_i$에 대해, 우리는 한 탐색이 $k_i$를 위한 것이 되도록 하는 확률 $p_i$를 가진다. 어떤 탐색은 $K$안에 있지 않는 값들일 지도 모르고, 그래서 우리는 $K$에 있지 않는 값을 나타내는 $d_0, d_1, d_2, \dots, d_n$의 $n + 1$개의 "dummy keys"를 가진다. 특히, $d_0$은 $k_1$보다 더 작은 모든 값을 나타내고, $d_n$은 $k_n$보다 더 큰 모든 값을 나타낸다. 그리고 $i = 1, 2, \dots, n - 1$에 대해, 그 dummy key $d_i$는 $k_i$와 $k_{i+1}$사이의 모든 값을 나타낸다. 각 dummy key $d_i$에 대해, 우리는 한 탐색이 $d_i$와 일치하는 한 확률 $q_i$를 가진다. 그림 15.9는 $n = 5$ keys의 한 집합에 대해 두 개의 binary search trees를 보여준다. 각 key $k_i$는 internal node이고, 각 dummy key $d_i$는 leaf이다. 모든 탐색은 성공하거나 (어떤 key $k_i$를 찾거나) 또는 성공하지 못하거나 (어떤 dummy key $d_i$를 찾거나) 둘 중 하나이고, 그래서 우리는 다음을 갖는다.

$$\sum^n_{i = 1} p_i + \sum^n_{i = 0} q_i = 1. \;\;\;\;\;\;\;\; (15.10)$$

각 key와 각 dummy key에 대한 탐색의 확률을 가지고 있기 때문에, 우리는 주어진 이진 탐색 트리 $T$에서의 탐색의 기대 비용을 결정할 수 있다. 우리가 한 탐색의 실제 비용이 조사되는 노드들의 개수와 같다고 가정해보자. 즉, $T$에서의 탐색에 의해 발견되는 노드의 깊이에 plus 1이다. 그러고나서 T에서의 탐색의 기대비용은 다음이다.

$$\begin{split} E [\text{search cost in } T] & = \sum^n_{i = 1} (depth_T(k_i) + 1) \cdot p_i + \sum^n_{ i= 0}(depth_T(d_i) + 1) \cdot q_i \\ & = 1 + \sum^n_{i=1} depth_T(k_i) \cdot p_i + \sum^n_{i=0} depth_T(d_i) \cdot q_i, \;\;\;\;\;\;\;\; \\(15.11) \end{split}$$

여기에서 $depth_T$는 tree $T$에서의 한노드의 깊이를 나타낸다. 그 마지막 항등식은 방정식 (15.10)으로 부터 따른다. 그림 15.9(a)에서, 우리는 노드마다의 expected search cost를 계산할 수 있다:

node	depth	probability	contribution
$k_1$	1	0.15	0.30
$k_2$	0	0.10	0.10
$k_3$	2	0.05	0.15
$k_4$	1	0.10	0.20
$k_5$	2	0.20	0.60
$d_0$	2	0.05	0.15
$d_1$	2	0.10	0.30
$d_2$	3	0.05	0.20
$d_3$	3	0.05	0.20
$d_4$	3	0.05	0.20
$d_5$	3	0.10	0.40
Total			2.80

확률의 한 주어진 집합에 대해, 우리는 expected search cost가 가장 작은 binary search tree를 구성하기를 원한다. 우리는 그러한 tree를 optimal binary search tree라고 부른다. 그림 15.9(b)는 그 그림 caption에서 주어지는 probabilities에 대해 optimal binary searchtree를 보여준다; 그것의 expected cost는 2.75이다. 이 예제는 한 optimal binary search tree가 반드시 전체 height가 가장 작은 트리가 아니라는 것을 보여준다. 그 뿐만 아니라, root에 가장 큰 확률을 가진 key를 항상 넣어서 optimal binary search tree를 반드시 구성할 수 없다. 여기에서, $k_5$는 어떤 key의 가장 큰 search probability를 가지지만, 보여지는 그 optmal binary search tree의 root는 $k_2$이다. ($k_5$가 root에 있는 어떤 binary search tree의 lowest expected cost는 2.85이다.)

matrix-chainmultiplication에서 처럼, 모든 가능성의 철저한 체크는 효율적인 알고리즘을 만드는데 실패한다. 우리는 한 binary search tree를 구성하기 위해 keys $k_1, k_2, \dots, k_n$을 가진 n개의 node의 binary tree의 노드들에게 label를 붙일 수 있고, 그러고나서 그 dummy keys를 leaves로 추가할 수 있다. 문제 12-4에서, 우리는 n개의 노드들을 가진 binary trees의 개수가 $\Omega(4^n / n^{3/2})$이 라는 것을 보았고, 그래서 우리는 exhaustive search에서 binary search trees의 exponential number를조사해야만 할 것이다. 놀랍지 않게, 우리는 dynamic programming으로 이 문제를 해결할 것이다.

 

Step 1 : The structure of an optimal binary search tree

optimal binary search trees의 optimal substructure를 특징화하기 위해, 우리는 subtrees에 대한 관찰로 시작한다. 한 binary search tree의 어떤 subtree를고려해보자. 그것은 어떤 $1 \leq i \leq j \leq n$에 대해 연속한 range $k_i, \dots, k_j$에 있는 keys를 포함해야 한다. 게다가, $k_i, \dots, k_j$를 포함하는 한 subtree는 또한 그것의 leaves로서 dummy keys $d_{i-1}, \dots, d_j$를 가져야만 한다.

이제 우리는 optimal substructure를 말할 수 있다: 만약 한 optimal binary search tree T가 keys $k_i, \dots, k_j$를 포함하는 subtree $T'$를 가진다면, 그러면 이 subtree $T'$는 keys $k_i, \dots, k_j$와 dummy $d_{i-1}, \dots, d_j$를 가진 subproblem에 대해서도 또한 optimal이여야 한다. 그 보통의 cut-and-past argument가 적용된다. 만약 $T'$의 expected cost보다 더 낮은 한 subtree $T''$가 있다면, 그러면 우리는 $T$에서 $T'$를 자르고, $T''$를 붙여넣을 수 있고, 이것은 $T$보다 더 낮은 expected cost의binary search tree를 만들고, 따라서, T의 optimality와 모순이 된다.

우리는 우리가 optimal solutions에서 subproblems까지 그 문제에 대한 optimal solution을 구성할 수 있다는 것을 보여주기 위해 그 optimal substructure를 사용할 필요가 있다. keys $k_i, \dots, k_j$가 주어진다면, 이러한 keys들 중 하나, 가령 $k_r (i \leq r \leq j)$가 이러한 keys들을 포함하는 optimal subtree의 root이다. 그 root $k_r$으 left subtree는 $k_i, \dots, k_{r-1}$의 keys를 포함한다 (그리고 dummy keys $d_{i-1}, \dots, d_{r-1}$), 그리고 right subtree는 keys $k_{r+1}, \dots, k_j$를 포함한다 (그리고 dummy keys $d_r, \dots, d_j$). 우리가 모든 candidate roots $k_r$를 조사하는 한, $i \leq r \leq j$에서, 우리는 $k_i, \dots, k_{r-1}$를 포함하는 모든 optimal binary search trees를 결정할 것이고, $k_{r+1}, \dots, k_j$를 포함하는 모든 binary search trees를 결정하는 한, 우리는 optimal binary search tree를 찾을 것이 보장되어진다.

"empty subtrees"에 대해 주의해야 할 가치가 있는 한 가지 세부사항이 있다. keys $k_i, \dots, k_j$를 가진 한 subtree에서, 우리는 $k_i$를 root로 선택한다고 가정하자. 위의 주장에 의해, $k_i$의 left subtree는 keys $k_i, \dots, k_{i-1}$를 포함한다. 우리는 이 sequence를 어떠한 keys를 포함하지않는 것으로 해석한다. 그러나, subtree가 또한 dummy keys를 포함할 수 있다는 것을 명심해라. 우리는 $k_i, \dots, k_{i-1}$를 가진 한 subtree가 어떠한 실제 keys를갖지 않지만, single dummy key $d_{i-1}$를 포함한다는 컨벤션을 채택한다. 대칭적으로 만약 우리가 $k_j$를 root로 선택한다면, 그러면 $k_j$의 right subtree는 keys $k_{j+1}, \dots, k_j$를 포함한다; 즉, 이 right subtree는 어떠한 실제 keys를 포함하지않지만, 그것은 dummy key $d_j$를 포함한다.

 

Step 2: A recursive solution

우리는 한 optimal solution의 value를 재귀적으로 정의할 준비가 되었다. 우리는 $i \geq 1, j \leq n, \text{ and } j \geq i - 1$에서 ($j = i - 1$일 때, 실제 키는 없고, dummy key $d_{i-1}$를 가진다.), keys $k_i, \dots, k_j$를 포함하는 optimal binary search tree를 찾는 것으로서 우리의 subproblem domain을 고른다. 우리가 keys $k_i, \dots, k_j$를 포함하는 한 optimal binary search tree를 탐색하는 expected cost로서 $e[i,j]$를 정의해보자. 궁극적으로, 우리는 $e[1,n]$을 연산하고 싶다.

그 가장 쉬운 경우는 $j = i - 1$일 때 발생한다. 그러고나서, 우리는 dummy key $d_{i-1}$를 가진다. 그 expected search cost는 $e[i, i - 1] = q_{i -1}$이다.

$j \geq i$일 때, 우리는 $k_i, \dots, k_{r-1}$을 가진 한 optimal binary search tree를 그것의 left subtree로, 그리고 keys $k_{r+1}, \dots, k_j$를 가진 한 optimal binary search tree를 그것의 right subtree로서 만들 필요가 있다. 한 subtree가 한 노드의 subtree일 때, 그것의 expected search cost는 무엇이 되는가? 그subtree에서 각 노드의 depth는 1씩 증가한다. 방정식 (15.11)에 의해, 이 subtree의 expected search cost는 그 subtree에 있는 모든 probabilities의 합만큼 증가한다. keys $k_i, \dots, k_j$를 가진 한 subtree에 대해, 우리가 이 probabilities의 합을 다음으로 표기하도록 하자

$$w(i,j) = \sum^j_{l = i} p_l + \sum^j_{l = i - 1} q_l. \;\;\;\;\;\;\;\;\;\; (15.12)$$

따라서, 만약 $k_r$이 $k_i, \dots, k_j$ 를 포함하는 한 optimal subtree의 root라고 한다면, 우리는 다음을 가진다

$$e[i,j] = p_r + (e[i, r-1] + w(i, r-1)) + (e[r+1, j] + w(r+1, j)).$$

다음을 주목하여

$$w(i,j) = w(i, r - 1) + p_r + w(r+1, j),$$

우리는 $e[i,j]$를 다시 다음으로 재작성한다

$$e[i,j] = e[i, r-1] + e[r + 1, j] + w(i, j). \;\;\;\;\;\; (15.13)$$

그 재귀 방정식 (15.13)은 우리가 root로서 어떤 노드 $k_r$를 사용할지를 안다고 가정한다. 우리는 가장 낮은 expected search cost를 주는 root를 선택하고, 이것은 우리에게 최종 recursive formulation을 준다:

$$e[i,j] = \bigg\{ \begin{split} & q_{i-1} \text{ if $j = i - 1$, } \\ & min_{i \leq r \leq j} \{e[i, r-1] + e[r + 1, j] + w(i, j) \} \text{ if $i \leq j$.} \end{split} \\ (15.14)$$

그 $e[i,j]$값들은 optimal binary search trees에서의 expected search costs를 준다. 우리가 optimal binary search trees의 구조를 추적하는 것을 돕기 위해, 우리는 $1 \leq i \leq j \leq n$에 대해 $root[i,j]$를 $k_i, \dots, k_j$를 포함하는 한 optimal binary search tree의 root인 $k_r$인 인덱스 $r$이 되도록 정의한다. 비록 우리가 $root[i,j]$의 값을 연산하는 방법을 볼지라도, 우리는 이러한 값들로부터 optimal binary search tree를 구성하는 것을 Exercise 15.5-1로 남겨둔다.

 

Step 3: Computing the expected search cost of an optimal binary search tree

이 시점에서, 너는 optimal binary search trees와 matrix-chain multiplication의 우리의 특징화 사이의 어떤 유사점을 눈치챘을지도 모른다. 두 문제 도메인에 대해, 우리의 subproblems은 연속하는 index subranges를 구성한다. equation (15.14)의 direct, recursive implementation은 direct, recursive matrix-chain multiplication algorithm만큼 비효율적이다. 대신에, 우리는 한 table $e[1..n+1, 0..n]$에 $e[i,j]$값을저장한다. 그 첫 번째 index는 n이라기보다는 n + 1번 작동할 필요가 있는데, 오직 dummy key $d_n$만을 가지는 한 subtree를갖기 위해서, 우리는 $e[n+1,n]$을 연산하고 저장할 필요가 있기 때문이다. 그 두 번째 인덱스는 0에서 시작할 필요가 있는데, dummy key $d_0$만을 포함하는 한 subtree를 가지기 위해, 우리는 $e[1,0]$을 연산하고 저장할 필요가 있기 때문이다. 우리는 $j \geq i - 1$에 대한entries $e[i,j]$만을 사용한다. 우리는 또한 $root[i,j]$를 사용하는데, keys $k_i, \dots , k_j$를 포함하는 subtree의 root를 기록하기 위해서이다. 이 테이블은 $1 \leq i \leq j \leq n$을 위한 entries만을 사용한다.

우리는 효율성을 위한 다른 테이블이 필요할 것이다. 우리가 $e[i,j]$를 연산할 때 마다, 처음부터 $w(i,j)$를 연산하기 보다, - $\Theta(j - i)$이 걸리는 - 우리는 이러한 값들을 한 table $w[1..n + 1, 0..n]$에 저장한다. 그 base case에 대해, 우리는 $1 \leq i \leq n + 1$를 위해 $w[i, i - 1] = q_{i-1}$를 연산한다. $j \geq i$에 대해, 우리는 다음을 연산한다

$$w[i,j] = w[i, j - 1] + p_j + q_j. \;\;\;\;\; (15.15)$$

따라서, 우리는 $\Theta(1) time$에 $w[i,j]$의 $\Theta(n^2)$개의 values를 각각 연산할 수 있다.

그 확률 $p_1, \dots, p_n$과 $q_0, \dots, q_n$, 그리고 size n을 입력으로 받는 다음의 슈도코드가 있는데, 이것은 tables $e$와 root를 반환한다.

xxxxxxxxxx
OPTIMAL-BST(p,q,n)
1   let e[1..n+1, 0..n], w[1..n + 1, 0..n],
            and root[1..n, 1..n] be new tables
2   for i = 1 to n + 1
3       e[i, i - 1] = q_{i-1}
4       w[i, i - 1] = q_{i-1}
5   for l = 1 to n
6       for i = 1 to n - l + 1
7           j = i + l - 1
8           e[i, j] = \infty
9           w[i, j] = w[i, j - 1] + p_j + q_j
10          for r = i to j
11              t = e[i, r - 1] + e[r + 1, j] + w[i, j]
12              if t < e[i, j]
13                  e[i, j] = t;
14                  root[i , j] = r
15  return e and root

위의 설명과 Sectino 15.2에서의 MATRIX-CHAIN-ORDER procedure와의 유사성으로 부터, 너는 이 절차의 연산이 꽤 간단하나다는 것을 발견할 것이다. lines2-4의 for loop는 $e[i, i- 1]$과 $w[i, i - 1]$의 값을 초기화한다. lines 5-14의 for loop는 (15.14)와 (15.15)의 반복을 사용하는데, 모든 $1 \leq i \leq j \leq n$에 대해 $e[i,j]$와 $w[i,j]$를 연산하기 위해서이다. 그 첫 번째 반복에서, $l = 1$일 때, 그 loop는 $e[i,i]$와 $w[i,i]$를 $i = 1, 2, \dots, n$에 대해서 연산한다. lines 10-14에 있는 가장 안쪽ㄱ의 for loop는 keys $k_i, \dots, k_j$를 포함하는 optimal binary search tree의 root로서 사용한 key $k_r$를 결정하기 이ㅜ해 각 candidate index $r$를 시도한다. 이 for loop는 그것이 root로서 사용할 더 좋은 key를 발견할 때 마다 $root[i,j]$에 있는 index r의 현재 값을 저장한다.

그림 15.10은 그림 15.9에서 보여지는 key 분포에서 procedure OPTIMAL-BST에 의해 연산되는 tables $e[i,j], w[i,j], root[i,j]$를 보여준다. 그림 15.5의 matrix-chain multiplication example에서 처럼, 그 테이블은 대각선이 수평하게 되도록 만들기 위해 회전된다. OPTIMAL-BST는 bottom에서 top으로 왼쪽에서 오른쪽으로 각 row내에서 rows를 연산한다.

OPTIMAL-BST procedure는 $\Theta(n^3)$ time이 걸린다, MATRIX-CHAIN-ORDER처럼. 우리는 쉽게 그것의 작동 시간이 $O(n^3)$이라는 것을 알 수 있는데, 그것의 for loops가 세 번 nested 되고, 각 loop index가 최대 n개의 값을 취하기 때문이다. OPTIMAL-BST에서 그 loop indices는 정확히 MATRIX-CHAIN-ORDER에서 있는 것처럼 같은 제한을 갖지 않지만, 그것들은 최대 모든 방향에서 1 이내에 있다. 따라서, MATRIX-CHAIN-ORDER처럼, 그 OPTIMAL-BST procedure는 $\Omega(n^3)$ time이 걸린다.

 

 

 

---

1 우리는 weigthed edges를 가진 shortest paths를 찾는 것과 이 문제를 구분하기 위해 "unweighted"라는 용어를 사용한다. 그 weighted edges를 가진 문제는 Chapters 24와 25에서 볼 것이다. 우리는 그 unweightd problem을 해결하기 위해 Chapter 22의 breadth-first search technique를 사용할 수 있다. ↩

2 dynamic programming이 subproblems이 independent하면서 overlapping하는 것에 의존하는 것은 이상한 것처럼 보일지도 모른다. 비록 이러한 요구사항이 모순되게 들릴지라도, 그것들은 같은 측면에서의 두 가지 요점이 아니라, 두 개의 다른 개념들을 설명한다. 같은 문제에 대한 두 개의 subproblems은 만약 그것들이 resources를 공유하지 않는다면 독립적이다. 두 개의 subprlbmes이 다른 문제의 subproblem으로서 발생하는 같은 subproblem이라면 overlapping한다. ↩

3 이 접근법은 모든 가능한 subproblem parameters의 집합을 알고 있고, 우리가 table positions과 subproblems사이의 관계를 구성했다고 미리 가정한다. 또 다른, 좀 더 일반적인, 접근법은 subproblem parameters를 keys로서 hashing하는 것을 사용하여 memoize하는 것이다. ↩