[ Algorithm ] 동적 계획 (3)
동적 계획
1) 프로이드의 최단경로 알고리즘
모든 점에서 모든 다른 점까지의 거리를 알아내는 알고리즘
$D^k$$[i][j]$= 집합 {v_1,v_2, v_3, … v_k}에 속하는 마디 만을 거쳐서 v_i 에서 v_j로 가는 최단 경로의 길이를 구한다.
$D^0$$[i][j]$는 다른 어떤 마디도 거쳐 가지 못하도록 하고 구한 최단 경로의 길이이므로, v_i 에서 v_j,를 잇는 이음선이 가중치이다. $D^0$= W, $D^n$= D
※ 배열 D 하나만 가지고 계산할 수 있는 이유는 k째 행과 k째 열에 있는 값들은 루프의 k째 반복을 실행하는 동안 변하지 않기 때문이다.
2) 동적 계획과 최적화 문제
최적의 원칙: 어떤 문제의 입력 사례의 최적해가 그 입력 사례를 분할한 부분 사례에 대한 최적해를 항상 포함하고 있으면, 그 문제는 최적의 원칙이 성립한다고 한다.
3) 연쇄 행렬 곱셈
(k − 1)째 행렬 A_(k-1) 과 k째 행렬 A_k를 곱하기 때문에 A_(k-1)의 열의 수는 A_k의 행의 수와 같아야 한다.
ex) 행렬 곱셈에서 첫째 행렬은 열의 수가 3이고, 둘째 행렬은 행의 수가 3이다. d_0을 A_1의 행의 수라 하고, 1 ≤ k ≤ n인 모든 k에 대해서 d_k를 A_k 열의 수라고 하면, A_k의 크기는 d_(k-1) X d_k 가 된다.
앞 절에서 본대로 해답을 구축하기 위해서 일련의 배열을 사용한다. 1 ≤ i ≤ j ≤ n인 모든 i와 j에 대하여 다음과 같이 재귀 관계식을 구축한다.
$M [i][j]$ =i < j 일 때,A_i 부터 A_j 까지 행렬을 곱하는데 필요한 원소 단위 곱셈의 최소 횟수 $M [i][i] = 0$이다.
6개의 행렬을 곱하는 최적의 순서는 다음과 같은 인수 분해 중 하나가 되어야 한다.
1. A_1 (A_2 A_3 A_4 A_5 A_6)
2. (A_1 A_2)(A_3 A_4 A_5 A_6)
3. (A_1 A_2 A_3)(A_4 A_5 A_6)
4. (A_1 A_2 A_3 A_4)(A_5 A_6)
5. (A_1 A_2 A_3 A_4 A_5)(A_6)
6. (A_1 A_2 A_3 A_4 A_5)A_6
여기서 각 괄호 안 행렬의 곱은 최적의 순서에 따라 구한 것으로, 이 인수분해 중 원소단위 곱셈의 횟수가 최소가 되는 것이 최적의 해가 됨이 틀림없다. k째 인수분해의 곱셈의 횟수는 각 인수를 구하는데 필요한 최소 원소단위 곱셈의 횟수 더하기 두 인수를 곱하는데 필요한 원소단위 곱셈의 횟수가 된다. 따라서 $M [1][k]$ + $M [k+1][6]$ + $d_0 d_k d_6$ 식으로 표현할 수 있다.
첫째 행렬은 A_1이고, 마지막 행렬은 A_6이 되어야 한다고 제한을 두지 않았다. 예를 들면 A_2부터 A_6를 곱해도 비슷한 결과를 얻을 수 있었을 것이다. 따라서 이 결과를 n개의 행렬을 곱하는 재귀 관계식으로 다음과 같이 일반화 할 수 있다.
1 ≤ i ≤ j ≤ n인 모든 i와 j에 대하여,
이 관계식에 기초한 분할정복 알고리즘은 지수시간이다. 동적계획법으로 $M [i][j]$의 값을 단계별로 구하는 효율적인 알고리즘을 설계,파스칼의 삼각형과 비슷한 형태의 격자를 사용하여 다음 특성을 기초로 하여 계산을 수행한다.
$M [i][j]$ 값은 $M [i][j]$와 같은 행에서 왼쪽에 있는 값 모두와 같은 열의 아래쪽에 있는 값 모두를 가지고 계산한다. 이 특성을 이용하면 M의 값을 모두 다음과 같이 계산할 수 있고, 먼저 대각선 상에 위치한 값을 모두 0으로 놓고, 다음에 대각선 바로 위에 위치한 값(대각선 1)을 모두 계산하고, 다음에 대각선 2에 위치한 값을 모두 계산하고, 등등 이런 식으로 최종 답인 대각선 5에 위치한 유일한 값 $M [i][j]$을 계산할 때까지 계속한다.
4) 최적 이분 검색 트리
원소를 찾는데 프로시저 search에서 수행한 비교의 횟수를 검색 시간이라고 한다. 현재 목표는 평균검색시간이 최소가 되는 트리를 찾아내는 것으로, while 루프를 한 번 반복할 때마다 한번씩 비교된다. 따라서 주어진 원소의 검색시간은 depth(key) +1 이 된다.
〖Key〗_1, 〖Key〗_2, …, 〖Key〗_n을 순서대로 나열한 n개의 원소라 하고, p_i 를 〖Key〗_i 가 검색키일 확률이라고 할 때, 주어진 트리에서 원소 〖Key〗_i를 찾는데 필요한 비교 횟수를 c_i 라고 하면 그 트리에 대한 평균 검색 시간은
동적계획으로 더 효율적인 알고리즘을 만들 수 있는데 〖Key〗_i 부터 〖Key〗_j까지의 원소들을 다음 식의 값이 최소가 되도록 트리에 배치했다고 가정 시,
여기서 c_m 은 그 트리에서 〖Key〗m을 찾는데 필요한 비교 횟수이다. 이러한 트리를 원소들에 대한 최적 트리라 하고, $A [i][j]$로 표시, 원소가 하나 있으면 트리에서 원소를 찾는데 비교를 한번 하므로, $A [i][j]$ = p_i
트리 n을 〖Key〗n이 뿌리여야 한다는 제한을 가진 최적트리라고 할때, 1 ≤ k ≤ n인 모든 k에 대해서 트리 k의 하위 트리는 반드시 최적이어야한다. 따라서 이 하위트리들의 평균검색시간은 그림에서 보여준다.
m ≠ k인 모든 m에 대해서 트리 k에서 〖Key〗m을 찾는데 수행하는 비교 횟수는 그 원소가 있는 하위 트리에서 그 원소를 찾는데 수행하는 비교 횟수보다 정확히 하나 더 많다.(여기에서 뿌리에서 추가적으로 한 번 더 비교) 이 한 번의 비교 때문에 트리 k에서 〖Key〗m을 찾는 평균 검색 시간은 1 X p_m 만큼 늘어난다.
5) DNA 서열 정렬
x$[0]$ = y$[0]$이면, 손해 penalty =0, 그렇지 않다면 손해가 1이라고 한다면,
- opt(0, 0) = min(opt(1, 1) + penalty, opt(1, 0) + 2, opt(0, 1) + 2).
- opt(i, j) = min(opt(i+1, j+1) + penalty, opt(i+1, j)+ 2, opt(i, j+1) + 2).
재귀 알고리즘을 만들기 위해 종료 조건 : 서열 x의 길이를 m, y의 길이를 n이라고 하면, 서열 x의 끝 지점(i=m)을 지났고 서열 y의 j지점(j<n)이 있다면, 틈을 n-j개 삽입해야 한다.
- opt(m,j) = 2(n-j).
비슷한 이치로 서열 y의 끝지점(j=n)을 지났고 서열 x의 i지점(i<m)에 있다면, 틈을 m-i개 삽입해야 한다.
- opt(i,n) = 2(m-i)
동적 계획으로 풀기 위해선 m+1, n+1 크기의 2차원 배열을 만들고, 틈의 행과 열에서 출발하여 위쪽으로 배열을 채워 나가며 반복 계산한다.
opt(i, j) = min(opt(i+1, j+1) + penalty, opt(i+1, j)+ 2, opt(i, j+1) + 2).
opt(10,j) = 2(8-j)
opt(i,8) = 2(10– i)
배열의 맨 아래 행의 opt(i,j) 값을 계산하라면 (2)식을 쓰고, 배열의 맨 오른쪽 열의 opt(i,j) 값을 계산하려면 (3)식을 쓰고, 나머지 경우에는 (1)식을 쓴다.
(1)식을 쓰는 경우 구하려는 칸의 바로 아래 칸의 값과 바로 오른쪽 칸의 값, 대각선으로 바로 아래 칸의 값을 가지고 계산한다.
ex) opt(6,5)는 opt(6,6)과 opt(7,5), opt(7,6)을 가지고 계산
1.배열의 오른쪽 맨 아래 구성에서 시작하여 표시해둔 경로를 따라간다.
2.배열의 $[i][j]$ 칸에 도달하기 위해서 대각선으로 이동할 때마다, i째 행에 해당하는 문자를 x서열에 넣고, j째 열에 해당하는 문자를 y서열에 넣는다.
3.배열의 $[i][j]$ 칸에 도달하기 위해서 위로 이동할 때마다, i째 행에 해당하는 문자를 x서열에 넣고, 틈 문자를 y서열에 넣는다.
4.배열의$[i][j]$ 칸에 도달하기 위해서 왼쪽으로 이동할 때마다 , j째 행에 해당하는 문자를 y 서열에 넣고, 틈 문자를 x 서열에 넣는다.
다음과 같은 최적 정렬 서열을 얻는다.
※손해 값을 다르게 잡으면 최적 정렬 서열이 다르게 나올 것이다.
출처: 알고리즘 기초