동적계획법과 최적화 문제 Dynamic Programming을 사용한 최적화 문제를 해결하는 알고리즘 설계 절차

Presentation on theme: "동적계획법과 최적화 문제 Dynamic Programming을 사용한 최적화 문제를 해결하는 알고리즘 설계 절차"— Presentation transcript:

1 동적계획법과 최적화 문제 Dynamic Programming을 사용한 최적화 문제를 해결하는 알고리즘 설계 절차
1단계: 문제의 입력에 대해서 최적(optimal)의 해답을 주는 재귀적 속성(recursive property)을 설정 2단계: 상향적으로 최적의 해답을 계산 예] Floyd 알고리즘에서 D, P 계산 3단계(Optional): 상향적으로 최적의 해답을 구축 예] Floyd 알고리즘에서 경로 출력 (path(index q, r)) Note: 이항 계수를 구하는 알고리즘 3.2는 최적화 문제가 아니다.

2 동적계획법과 최적화 문제 [주의]모든 최적화 문제를 동적 프로그래밍으로 해결할 수 있는 것은 아니다.
주어진 문제에 대해 최적의 원칙이 적용될 수 있어야 동적 프로그래밍으로 해결할 수 있다. 어떤 문제의 사례에 대한 최적 해가 그 사례를 분할한 부분사례에 대한 최적 해를 항상 포함하고 있으면, 그 문제는 최적의 원칙(The Principle of Optimality)이 적용된다 라고 한다.

3 최적의 원칙 (The Principle of Optimality)
[예] 최단경로를 구하는 문제에서, vk를 vi에서 vj로 가는 최적 경로 상의 중간 정점이라고 할 때, - vi에서 vk 까지의 부분 경로: vi에서 vk 까지에 대한 최단경로 구하는 문제의 최적해 - vk에서 vj 까지의 부분 경로: vk에서 vj 까지에 대한 최단경로 구하는 문제의 최적해 - 즉, 어떠한 사례에 대한 최적 해는 모든 부분사례에 대한 최적해를 포함 하기 때문에 최적의 원칙을 준수한다고 볼 수 있다. 이는 재귀적 속성이 가져야 할 기본 원리 재귀적 속성이 만들어지면 Dynamic Programming을 사용하여 주어진 문제를 풀 수 있다.

4 최적의 원칙 (The Principle of Optimality)
주어진 다음의 그래프에서 v2에서 v1으로 가는 최종적인 최단 경로는 다음과 같다. v2  v4  v5  v1 위 최단 경로 중 v2에서 v5 까지 가는 부분 경로는 다음과 같으며, v2  v4  v5 위 부분 경로 역시 v2에서 v5 까지의 최단경로이다. 모든 경우에 대해 위와 같은 성질이 만족하면 “최적의 원칙”을 만족하게 되며, 또한 동적 프로그램 알고리즘을 구축할 수 있다. v5 v1 v4 v2 v3 3 5 1 9 2 4

5 최적의 원칙이 적용되지 않는 예제 최장경로(Longest Path) 문제 v1 v2 v3 v4
가정: 문제에 대한 해를 단순 경로 (Simple Path)로 제한 v2 3 v3 v1 v4 1 2 4 v1에서 v4로의 최장경로는 [v1, v3, v2, v4]가 된다. Length([v1, v3, v2, v4])=8 그러나, 이 경로의 부분 경로인 v1에서 v3으로의 최장경로는 [v1, v3]이 아니고, [v1, v2, v3]이다. Length([v1, v3])=1 Length([v1, v2, v3])=4 따라서 최장경로 문제는 최적의 원칙이 적용되지 않는다.

6 연쇄행렬곱셈 (Matrix-Chain Multiplication)(1/3)
i  j 행렬과 j  k 행렬을 곱하기 위해서는 일반적으로 i  j  k번 만큼의 기본적인 곱셈이 필요하다. j번의 곱셈을 총

7 연쇄행렬곱셈 (Matrix-Chain Multiplication)(2/3)
연쇄적으로 행렬을 곱할 때, 어떤 행렬곱셈을 먼저 수행하느냐에 따라서 필요한 기본적인 곱셈의 횟수가 달라지게 된다. 예를 들어서, 다음 연쇄행렬곱셈을 생각해 보자: A1  A2  A3 A1의 크기는 10  100이고, A2의 크기는 100  5이고, A3의 크기는 5  50라고 하자. A1  A2를 먼저 계산한다면, 기본적인 곱셈의 총 횟수는 7,500회 (10 * 100 * 5) + (10 * 5 * 50) = 5, ,500 = 7,500 A2  A3를 먼저 계산한다면, 기본적인 곱셈의 총 횟수는 75,000회 (100 * 5 * 50) + (10 * 100 * 50) = 25, ,000 = 75,000

8 연쇄행렬곱셈 (Matrix-Chain Multiplication)(3/3)
 알고리즘 개발 목표: n개의 행렬(A1 , A2 ,…, An) 을 연쇄적으로 곱할 때 기본적인 곱셈의 횟수가 가장 적게 되는 최적의 순서를 결정

9 연쇄행렬곱셈 – Brute-Force Algorithm
알고리즘: 가능한 모든 순서를 모두 고려해 보고, 그 중에서 곱셈 연산의 수가 가장 최소인 것을 택한다. 시간복잡도 분석: 최소한 지수(exponential-time) 시간 증명: n개의 행렬(A1 , A2 ,…, An)을 곱할 수 있는 모든 순서의 가지 수: tn 만약 A1이 마지막으로 곱하는 행렬이라고 하면, 행렬 A2 ,…, An을 곱하는 데는 tn-1개의 가지수가 있을 것이다. An이 마지막으로 곱하는 행렬이라고 하면, 행렬 A1,…, An-1을 곱하는 데는 또한 tn-1개의 가지수가 있을 것이다. 그러면, tn  tn-1 + tn-1 = 2 tn-1이고, t2= 1이라는 사실은 쉽게 알 수 있다. 따라서 tn  2tn-1  22tn-2  …  2n-2t2 = 2n-2 이다.

10 연쇄행렬곱셈 –최적의 원칙 A1 ((((A2 A3) A4) A5) A6) (A2 A3) A4
최적의 원칙(Principle of Optimality)이 성립하는가?  n개의 행렬을 곱하는 최적의 순서는 n개의 행렬 중 일부 부분집합에 속하는 행렬을 곱하는 최적의 순서를 항상 포함한다 예를 들어, 6개의 행렬(A1 , A2 ,…, A6)을 곱한다고 가정할 때 최적해가 다음과 같다면, 3개의 행렬(A2 , A3 , A4)을 곱하는 최적의 순서는 다음과 같다.  그러므로, “최적의 원칙”을 만족하게 되며, 또한 동적 프로그램 알고리즘 을 구축할 수 있다. A1 ((((A2 A3) A4) A5) A6) (A2 A3) A4

11 DP 기반 연쇄행렬곱셈 – 설계 (1/2) n개의 행렬(A1 , A2 ,…, An)을 연쇄적으로 곱할 때, dk를 행렬 Ak의 열(column)의 수라고 정의하면 dk-1는 행렬 Ak-1의 열의 수 자연히 Ak의 행(row)의 수는 dk-1가 된다. A1의 행의 수는 d0라고 하자. 그렇다면, 간단하게 (A1A2)A3의 곱셈 연산 횟수는? d0d1d2 + d0d2d3

12 DP 기반 연쇄행렬곱셈 – 설계 (2/2) 우선, 다음의 M[i][j]를 정의
M[i][j] = Ai부터 Aj까지의 행렬을 곱하는데 필요한 곱셈의 최소 횟수 (if 1  i < j  n) = 0 (if i == j ) 따라서, 최적의 순서에 대한 곱셈의 최소 횟수는 다음과 같다.

13 DP 기반 연쇄행렬곱셈 – 설계 (2/2) 그러면, 다음과 같이 재귀적 속성을 구축할 수 있다. 일반화된 재귀적 속성
k = i, i+1, ..., j-2, j-1 M[i][j] = Ai부터 Aj까지의 행렬을 곱하는데 필요한 곱셈의 최소 횟수 (if 1  i < j  n) = 0 (if i == j )

14 DP 기반 연쇄행렬곱셈 – 재귀식 적용 예 d0 d d1 d d2 d d3 d d4 d d5 d6 위와 같은 6개의 행렬의 부분집합인 3개의 행렬(A4 , A5 , A6)을 곱하는 순서는 다음과 같이 2가지 경우가 있다. 1. A4 (A5 A6) 2. (A4 A5) A6 그러므로, 3개의 행렬(A4 , A5 , A6)을 곱하는 최적의 순서에 대한 최소 곱셈의 수는 다음과 같다.

15 DP 기반 연쇄행렬곱셈 – 재귀식 적용 예 대각선 1 대각선 2 대각선 3 대각선 4 대각선 5 즉, 행렬 M은 M[i][i]을 모두 0으로 세팅한 이후 대각선 1, 대각선 2, 대각선 3, … 순으로 각 원소를 계산한다.

16 DP 기반 연쇄행렬곱셈 – 최적 순서의 구축 (A1 A2 A3 A4 A5 A6) (A1(A2 A3 A4 A5 A6))
최적 순서를 얻기 위해서는 M[i][j]를 계산할 때 최소값을 주는 k값을 P[i][j]에 기억한다. 예: P[2][5] = 4인 경우의 최적 순서는 (A2 A3 A4)A5이다. 구축한 P는 다음과 같다. 따라서, 최적의 행렬 곱셈 순서는 (A1((((A2 A3) A4) A5) A6))이다. (A1(A2 A3 A4 A5 A6)) (A1((A2 A3 A4 A5) A6)) (A1(((A2 A3 A4) A5) A6)) (A1((((A2 A3) A4) A5) A6)) (A1 A2 A3 A4 A5 A6)

17 DP 기반 연쇄행렬곱셈 – 알고리즘 (1/2) 문제: n개의 행렬을 곱하는데 필요한 기본적인 곱셈 횟수의 최소치를 결정하고, 그 최소치를 구하는 순서를 결정하라. 입력: 행렬의 수 n, 배열 d[0..n] (d[i-1]  d[i]는 i번째 행렬의 ”행의 수 * 열의 수”를 나타낸다.) 출력: 기본적인 곱셈 횟수의 최소치를 나타내는 minmult; 최적의 순서를 얻을 수 있는 배열 P (여기서 P[i][j]는 행렬 i부터 j까지가 최적 순서로 갈라지는 기점을 나타낸다.)

18 DP 기반 연쇄행렬곱셈 – 알고리즘 (2/2) [알고리즘 3.6](p.110)
int minmult(int n, int[] d, index[][] P){ index i, j, k, diagonal; int[][] M = new int[1..n][1..n]; for(i=1; i <= n; i++) M[i][i] = 0; for(diagonal = 1; diagonal <= n-1; diagonal++) for(i=1; i <= n-diagonal; i++) { // i: row j = i + diagonal; // j: column M[i][j] = minimum (M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j]); ikj-1 P[i][j] = 최소치에 해당하는 k의 값 } return M[1][n];

19 DP 기반 연쇄행렬곱셈 – 알고리즘 분석 단위연산: 각 k을 얻기 위하여 실행되는 명령문(instruction), 여기서 최소값인 지를 알아보는 비교문도 포함한다. 입력크기: 곱하려는 행렬의 수 n 분석: j = i + diagonal이므로, k-루프를 수행하는 횟수 = i-루프를 수행하는 횟수 = n – diagonal diagonal의 범위는 1 ~ (n-1)이므로, 모든 경우 시간 복잡도는…

20 DP 기반 연쇄행렬곱셈 – 최적 해의 출력 문제: n개의 행렬을 곱하는 최적의 순서를 출력하시오.
입력: 정적인 입력  n과 앞서 구한 2차원 배열 P 동적인 입력  i, j(i번째 부터 j번째 까지의 행렬 곱셈을 의미) 출력: 최적의 순서 [알고리즘3.7] (p. 112): 복잡도 분석: T(n)  (n)  Why? void order(index i, index j){ if (i == j) System.out.print(“A” + i); else { k = P[i][j]; System.out.print(“(”); order(i,k); order(k+1,j); System.out.print(“)”); }

21 DP 기반 연쇄행렬곱셈 – 개선된 솔루션 Yao(1982)  (n2)
Hu and Shing(1982, 1984)  (n lg n)