how to solve it, ch4

 탐욕 알고리즘은 말 그대로 각 답의 도출 과정마다 최고로 이득이 큰 방향을 찾아가는 알고리즘이다. 개념이 단순하여 인기가 꽤 있다. 하지만 문제는 각 단계별로 최적의 답을 찾아주는 방법을 알고있다고 가정하기 때문에 이 부분이 복잡해 질 수도 있다. 또한 앞서도 언급했듯이 각 단계의 최적이 전체적으로 최적이 아닐 수도 있다.
 TSP의 경우, 현재 위치에서 가장 짧은 거리를 갖는 다음 도시로 가는 방법을 반복하는 것이 탐욕 알고리즘의 한 예이다.

 어떤 복잡한 문제가 있을 때, 그 문제를 직접 풀기보다 작은 단위로 나누어 푸는 것도 한 방법일 수 있다. D&C는 말 그대로 문제를 나누어 풀고 그 답을 합치는 방식이다. 알고리즘의 흐름은 다음과 같다.

1. 문제 $P$를 하부 문제 $P_1, P_2, … , P_k$로 나눈다.
2. 문제 $P_i$의 크기가 $rho$보다 작으면 문제를 풀고, 아니라면 다시 나눈다.
3. 나누어진 문제의 답을 최종 답으로 합친다.

 이 알고리즘의 예로 다음의 문제를 풀어볼 수 있다. $2^m times 2^m$의 격자를 갖는 체스판에 하나의 구멍이 임의로 뚫려있다. 이 판을 꺾여있는 L 모양의 타일로 꽉 채우려면 어떻게 해야할까? 우선 판을 크게 네 개의 정사각형으로 나누어본다. 그 후, 구멍이 있지 않은 세 조각에 걸치도록 L 형태의 타일을 배치한다. 그리고 네 개의 정사각형을 다시 네 개로 나눈다. 이 때, 타일을 하나의 구멍으로 생각하고 타일이 존재하지 않는 세 면에 걸치도록 L 형태의 타일을 다시 배치한다.

 위의 작업을 반복하다보면, 결국 아래의 그림처럼 하나의 타일을 넣을 공간만 남고 모두 채워지게 된다.

 마지막으로 빈 칸에 타일을 채워 넣으면 원하는 답을 얻을 수 있다. 이 방식이 바로 Divide and Conquer이다.

 동적 프로그래밍은 내가 현재 위치한 곳과, 앞으로 가야할 곳의 ‘중간지점’에 어떠한 작업을 함으로써 전체 문제의 해답을 얻을 수 있다는 원리에 바탕을 두고 있다. 다음 중간 점은 이전에 처리를 거친 점들의 함수로 표현하는데, 이런 면에서 재귀적(recursive)인 방법이라 할 수 있다. 동적 프로그래밍으로 풀 수 있는 문제는 다음의 특징들을 가지고 있다.

1. 문제를 다양한 단계(stage)에서 만들어지는 일련의 결정(decision)의 조합으로 나눌 수 있다.
2. 각각 단계는 몇 가지의 가능한 상태(state)가 있다.
3. 결정을 내리면 현 단계의 한 상태에서 다음 단계의 어떠한 상태로 이동한다.
4. 어떤 단계에서의 결정의 최적 조합(policy)는 이전 단계의 결정과 독립적이다.
5. 단계를 건너 발생하는 상태의 이동에 대한 비용(cost)가 잘 정의되어있다.

 이 방법은 마지막 목표점에서 시작하여 현재 지점까지 뒤로 진행하여 문제를 푼다. 즉, 제일 마지막 단계에서 최선의 선택을 할 것이라고 가정하고, 마지막 직전 단계에서 내릴 수 있는 최적의 선택을 한다. 이런 방법으로 현재 지점까지 진행하여 문제를 푸는 것이다.
 이 방법을 이해할 수 있는 가장 쉬운 예제는 ‘마차 문제’이다. 하나의 마차를 몰고 지정된 지점에 도착하기 위한 최적의 경로를 구하는 문제인데, 아래의 그림처럼 구성이 되어있다고 하자.

 1번 지점에서 출발하여 10번 지점까지 간다고 하자. 그럼 마부에게 선택권이 있는 단계는 총 4개 중 3개이다. 각 단계에서 다음 단계의 지점으로 가기위한 비용은 다음 그림과 같다.

 문제를 풀기 위해 몇 가지 용어를 정해야 한다.

1. $n$ 개의 단계가 있고, $n$ 번째 단계에서 다음에 어떤 상태로 이동할지에 대한 결정을 $x_n$이라 한다. 이 문제에서 $n$은 4이다.
2. 마부가 $n$ 단계의 $s$ 상태에 있고 $x_n$을 다음 중간 상태로 결정한다고 하자. 이 때, 모든 남은 단계에 대해서 내릴 수 있는 ‘결정의 최적 조합(policy)’의 비용을 $f_n(s, x_n)$으로 표현한다.
3. $x_n^{*}(s)$는 $f_n(s, x_n)$을 최소화하는 $x_n$의 값이다. 그리고 $f^{*}_n(s)$는 해당하는 최소값이다.
4. 문제의 목표는 $f_1^{*}(1)$을 찾는 것이다. 이는 $f_4^{*}(s), f_3^{*}(s), f_2^{*}(s)$를 찾는 것으로 구할 수 있다.

 그럼 이제 $f_4^{*}(s)$를 먼저 찾아야 한다. 그런데 사실 $n=4$일 때 선택권은 $x_n=10$ 밖에 없다. 그러므로 $s=8$일 때 비용 3, $s=9$일 때 비용 4를 갖는다. 이제 $f_3^{*}(s)$를 보자. 결정은 단계별로 독립적이므로 $f_3$는 아래의 식으로 표현할 수 있다.
$$
f_3(s, x_3) = c_{sx_3} + f_4^{*}(s)
$$
여기서 $c_{sx_3}$은 상태 $s$에서 $x_3$으로 상태를 결정하여 움직이는 비용이다. $s$가 5, 6, 7일 때, 선택지는 8과 9이다. 각 상태에서 각각 선택의 비용을 테이블로 표현하면 다음과 같다.
$$
begin{array}{c | c c | c c}
s & f_3(s, 8) & f_3(s, 9) & f_3^{*}(s) & x^{*}_3 \ hline
5 & 4 & 8 & 4 & 8 \
6 & 9 & 7 & 7 & 9 \
7 & 6 & 7 & 6 & 8 \
end{array}
$$
 이 작업을 $n=2$일 때 수행해보자. 그럼 출발 가능한 $s$는 2, 3, 4이고, 가능한 선택지 $x_2$는 5, 6, 7이다. 각각의 비용을 테이블로 나타내면 다음과 같다.
$$
begin{array}{c | c c c | c c}
s & f_2(s, 5) & f_2(s, 6) & f_2(s, 7) & f_2^{*}(s) & x^{*}_2 \ hline
2 & 11 & 11 & 12 & 11 & 5 text{or} 6 \
3 & 7 & 9 & 7 10 & 7 & 5\
4 & 8 & 8 & 11 & 8 & 5 text{or} 6\
end{array}
$$
 마지막으로 $s=1$일 때를 생각해보면 다음의 테이블로 표현할 수 있다.
$$
begin{array}{c | c c c | c c}
s & f_1(s, 2) & f_1(s, 3) & f_1(s, 4) & f_1^{*}(s) & x^{*}_1 \ hline
1 & 13 & 11 & 11 & 11 & 3 text{or} 4 \
end{array}
$$
 이 결과를 이용하면 $s=1$에서 출발하여 3, 또는 4를 거쳐 가는 길이 비용 11로 동일함을 알 수 있다. 그래서 결과적으로 다음의 세 가지 답안이 가능하다.

• 1 - 3 - 5 - 8 - 10
• 1 - 4 - 5 - 8 - 10
• 1 - 4 - 6 - 9 - 10

 앞서 소개한 내용 외에도, 책에서 ‘Branch and Bound’ 방식과 ‘A* algorithm’이 소개되어 있다. 하지만 개인적으로 크게 사용하는 곳을 보지 못했으므로, 블로그 포스트에는 넣지 않겠다.(이해를 제대로 못해서 그런건 절대 아니라고 … 하고 싶다…)