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

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

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

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

3 최적의 원칙 (The Principle of Optimality)
[예] 최단경로를 구하는 문제에서, vk를 vi에서 vj로 가는 최적 경로 상의 중간 정점이라고 할 때, {v1, v2,…, vk-1} 이렇게 되면 최적의 원칙을 준수하므로 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번 만큼의 기본적인 곱셈이 필요하다.

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가 된다.

12 DP 기반 연쇄행렬곱셈 – 설계 (2/2) A1의 행의 수는 d0라고 하자. 그러면, 다음과 같이 재귀적 속성을 구축할 수 있다. M[i][j] = i < j일 때 Ai부터 Aj까지의 행렬을 곱하는데 필요한 곱셈의 최소 횟수 (1  i < j  n) 따라서, 최적의 순서에 대한 곱셈의 최소 횟수는 다음과 같다.

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

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)

22 트리 (Logical) Data Structures Linear list Tree Graph Linear structures
Non-linear structures

23 트리 Definitions 트리의 높이(Height), 깊이(Depth), 수준(Level)
루트 노드에서 가장 멀리있는 말단노드까지 가는 유일한 경로상에 있는 노드의 개수 루트 노드는 깊이가 0이고 수준 0에 있다. (=4) Data Structure

24 이진 검색 트리 이진검색트리(binary search tree): 순서가 정의되어 있는 키 값을 노드로 지니는 이진 트리로서 다음과 같은 특성을 가지고 있다. 각 노드는 키를 가지고 있다. 한 노드의 키는 그 노드의 왼쪽 부분트리에 있는 노드들의 모든 키보다 크다. 한 노드의 키는 그 노드의 오른쪽 부분트리에 있는 노드들의 모든 키보다 크다.

25 이진 검색 트리 이진검색트리의 예 Which is/are binary search tree(s)? 15 20 25 12 10
22 5 30 40 2 60 70 80 55

26 이진 검색 트리 Balance Factor Balanced Binary (Search) Tree
: the height of the left subtree : the height of the right subtree Balanced Binary (Search) Tree A tree with |B|  1 for all nodes HL HR

27 이진 검색 트리 균형 최악의 경우 탐색은 Leaf Node까지 왼쪽 트리는 완전한 균형.
오른쪽 트리는 루트노드를 기준으로 왼쪽 서브트리 Height: 0(빈 트리), 오른쪽 서브트리 (Root가 Kim인 트리) Height: 5로서 균형이 현저히 무너져 있음 최악의 경우 탐색은 Leaf Node까지 왼쪽 트리는 최악의 경우에도 높이가 3. 오른쪽 트리는 최악의 경우 높이 6를 모두 타고 내려와야 함. 오른쪽 트리는 연결 리스트(Linked List)에 가까움. 연결이 한쪽으로 일직선으로(Linear Structure) 진행하는 트리  편향 이진트리 (Skewed Binary Tree) Data Structure