Dynamic Programming

 

* 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

 

Greedy : 근시안적으로 그때 그때 좋은 상태를 선택

Divide-and-conquer : 문제를 sub-problem으로 break up하여 독립적으로 해결

Dynamic programming : 문제를 overlapping sub-problem으로 break up

 

Weighted Interval Scheduling

각 job들은 weight를 가지고 있음. 각 job이 같은 시간에 overlap하지 않으면서 maximum weight subset을 찾는 문제이다.

 

모든 weight가 1일때에는 Interval scheduling 문제이므로 greedy algorithm으로 해결 가능. 하지만, weighted interval scheduling 문제의 경우 greedy algorithm으로 풀기 불가 (반례 존재)

 

 

 

 

위의 문제는 DP (Dynamic programming)으로 해결할 수 있으며, 알고리즘은 아래와 같다.

 

 

 

 

M[j] : 1~j까지의 job에대해 optimal solution을 모아놓은 데이터 구조, 바로 이전에 선택된 job을 저장해 놓는다.

j까지 job에 대한 optimal 값을 memoization한다.

 

p(j)는 j job의 바로 직전 job을 가르킨다.

먼저 finish time에 따라 job을 sorting하고 strart time에 대해서도 sorting함으로써 p(j)를 정한다.

 

j 번째 job에서 j job이 선택되냐 안되느냐에 따라 M[j]가 바뀐다.

1. j가 선택되었을 때, $v_j + p(j)$의 optimal solution

2. j가 선택되지않았을 때, 바로 직전의 j-1 job에 대한 optimal solution

두 case에서 weight값이 max가 되는 case를 선택한다.

 

 

 

 

위의 알고리즘의 iterative algorithm으로 bottom-up 방식으로 작성한 알고리즘이다.

 

 

Running time

Sorting하는데 $O(nlogn)$의 시간, M array를 계산하는데 $O(n)$의 시간이 소요된다.

pre-sorted 환경에서 running time은 $O(n)$이다.

 

 

M matrix를 계산했으면 이에 해당되는 job subset을 구행한다. 이는 p(j)를 통해 추적이 가능하고 알고리즘은 아래와 같다. (Find-Solution(j))

 

 

 

 

 

Segmented Least Squares

Least squares

Squared error의 합을 최소로하는 line을 찾는 문제이다. 즉, 아래 식을 최소로 하는 a, b를 찾는 문제이다.

 

 

n개의 $x_i, y_i$\에 대해서 a, b의 값은 아래 식을 통해 계산할 수 있다.

Running time은 $O(n)$이다.

 

 

 

Segmented least squares

n개의 data에 대해 L개의 line으로 squared error가 최소가 되게 하는 문제이다. Line이 많으면 많을수록 error가 작아지기 때문에 line 개수에 대한 penalty가 필요하다. 그렇기 때문에 regularization term을 추가하여 아래의 식을 최소화하는 문제로 정의할 수 있다.

 

function : $E + cL$

 

$E$는 SSE, $L$은 line의 개수, $c$는 가중치이다.

이 문제는 DP를 통해 풀수 있다.

 

j번째 point에서 어떤 것을 선택하느냐를 생각해보자. M[j] ( OPT(j) )는 point 1~j까지 minimum cost를 뜻한다. e(i, j)는 i~j point 사이의 SSE를 뜻한다.

 

그러면 j번째 point에서, 1~j번째 사이의 i를 결정하여 1~i, i~j 2개의 line을 만들도록 하는 i를 선택하는 문제가 된다.

 

 

 

 

이를 푸는 알고리즘은 아래와 같다.

 

 

 

 

첫번째 for문 : 모든 i~j points에 대해 error를 계산한다. 위에서 언급한 least square 방식으로 a, b 계수를 구하고 그에 대한 error를 계산하는 과정이 포함되어 있다. 하나의 i~j points에 대해 $O(n)$이 걸리므로 총 $O(n^3)$의 running time이 걸린다.

 

두번째 for문 : j를 증가시키면서 segemented minimum error M[j]을 업데이트한다. 1~j사이의 i를 찾는데 $O(n)$이 걸리므로 총 $O(n^2)$의 running time이 걸린다.

 

 

Running time

첫번째 for문이 bottleneck이므로 $O(n^3)$

 

 

 

Knapsack Problem

n개의 object는 각각 value와 weight가 정해져있다. 그리고 바구니(knapsack)이 있는데 담을 수 있는 weight가 정해져있다. (weight는 정수값임) 이 때, 무게 제한을 넘지 않으면서 total value가 최대가 되도록하는 subset을 구하는 문제이다.

 

이 문제는 greedy algorithm으로 풀 수 없다. (반례 존재)

 

 

OPT(i, w) : weght limit가 w일 때, 1~i의 objects들이 주어졌을 때 maximum profit

 

i 번째 object일 때 이를 담을 것이냐 말 것이냐 정해야한다.

이 때, i 번째 object가 weight limit을 넘을 경우, i-1 번째일 때를 고려한다.

weight limit을 넘지 않을 경우, i 번째 object를 선택했을 때, 선택하지 않았을 때 둘 중 profit이 높은 것을 선택한다.

이를 식으로 나타내면 아래와 같다.

 

 

 

 

OPT(i, w)인 M[i, w] array를 채우는 알고리즘은 아래와 같다. (bottom-up)

 

 

 

 

Running time

O(nW)

input size에 polynomial하지 않음 => Pseudo-polynomial

 

 

 

Shortest Paths

앞선 포스팅에서는 edge의 cost가 모두 양수일때 Dijkstra algorithm, greedy algorithm으로 해결하였다. 하지만, negative edge cost가 존재한다면 greedy 방법은 통하지 않는다. 여기서는 negative edge가 존재할 경우를 살펴본다.

 

우선, edge의 합이 음수가 되는 negative cost cycle이 존재할 경우, shortest path가 존재하지 않는다. 왜냐하면, 그 cycle을 계속 돌기만 해도 $- \infty$로 cost가 낮아지기 때문이다.

 

DP를 이용한 알고리즘에서는 s -> t path에서 반대로, t로부터 점점 넓혀나간다.

 

$OPT(i, v)$ : i개의 edge들을 이용한 shortest v-t path

 

v에서 i개의 edge를 이용해서 optimal path를 찾는것은, v직전의 모든 vertex (w)에 대해 path를 고려하는 문제로 쪼갤 수 있다. i-1개 edge를 사용하는 모든 경로에 대해 cost를 계산한다. 식으로 나타내면 다음과 같다.

 

 

 

 

i는 0 ~ n-1 까지 존재하고 v역시 0 ~ n-1까지 존재하므로, space는 $O(n^2)$필요하다. 그리고 이를 채우는 알고리즘은 다음과 같으며 time complexity는 $O(mn)$이다.

 

 

 

 

Practical improvements

1. M[i-1, v]만 사용하고 M[i-2, v], M[i-3, v], ... 는 사용하지 않으므로 길이가 n인 배열만 재사용한다.

2. 그리고 이 배열이 변하지 않으면 조기 종료한다.

 

변하지 않았으면, 다음 iteration에도 같은 것을 보기 때문에 더이상 상태가 변하지 않음. M[i, w]가 저번에도 변하지 않았다면, w와 관련되어 있는 path가 모두 고려되었기 때문에 w는 더이상 고려할 필요가 없다.

 

 

위 방법을 사용하면 memory는 $O(n)$이고, running time은 worst case일 때 $O(mn)$이고 왠만해서는 그전에 종료된다. 수정된 알고리즘은 아래와 같다.

 

 

 

 

 

Detecting Negative Cycles

$OPT(n, v) < OPT(n-1, v)$ 이면 negative cost cycle이 존재한다.

 

Pf )

$OPT(n, v)$는 정확히 n개의 edge를 사용한 cost의 합이다. Vertex는 n개이므로, n개의 edge를 사용하면 cycle은 무조건 존재한다. 그 cycle을 W라하자. 그리고 그 cycle를 돌지않고 v -> t 로 지나가는 path를 P', cycle을 한번돌고 지나가는 path를 P라하자.

 

OPT 정의에 의해, 그리고 P'는 n-1개보다 edge를 적게 썼기 때문에 다음이 성립한다.

 

$OPT(n, v) < OPT(n-1, v) \le c(P')$

 

그리고 $OPT(n, v) = c(P) = c(P') + c(W)$가 성립하기 때문에,

 

$c(P') + c(W) < c(P')$

$c(W) < 0 $

 

Negative cost cycle이 존재한다.

 

 

이를 실제로 알고리즘으로 구현하기 위해, 가상의 도착점 t를 둔다. 그리고 t는 모든 노드와 cost 0인 edge를 두고, 이 그래프에 대해 앞서 설명했던 알고리즘을 실행하면 negative cycle을 검출할 수 있다.