[강의정리] 알고리즘 W6 (Dynamic Programming)

---

Dynamic programming

• Similar to divide-and-conquer
• small instances first, store the results, whenever we need a result, look it up instead of recomputing it.

알고리즘: Using Divide-and-Conquer

• 문제: 이항계수를 계산한다
  • 입력: 음수가 아닌 정수 n과 k, 여기서 k <= n
  • 출력: bin, [n k]

int bin(int n, int k) {
  if (k == 0 || n == k)
    return 1;
  else
    return bin(n-1, k-1) + bin(n-1, k);
}

시간복잡도 분석:

• 분할정복 알고리즘은 작성하기는 간단하지만, 효율적이지 않음
  • 이유? 재귀호출(recursive call)할때 같은 계산을 반복해서 수행하기 때문
  • 예를 들면, bin(n-1, k-1)과 bin(n-1, k)는 둘다 bin(n-2, k-1)의 결과가 필요한데, 따로 중복 계산이 됨

[n: k]를 구하기 위해서 이 알고리즘이 계산하는 항(term)의 개수는 2[n: k]-1이다. (증명을 해보자)

증명: (n에 대한 수학적 귀납법으로 증명)

• 귀납출발점: 항의 개수 n이 1일 때 2[n: k]-1 = 2 x 1 - 1 = 1이 됨을 보이면 된다.

         [1: k]는 k=0이나 1일때 1이므로 항의 개수는 항상 1이다.
  

• 귀납가정: [n: k]를 계산하기 위한 항의 개수는 2[n: k] - 1이라고 가정한다.
• 귀납절차: [n+1: k]를 계산하기 위한 항의 개수가 2[n+1: k] - 1임을 보이면 된다.

       알고리즘에 의해서 [n+1: k] = [n: k-1] + [n: k] 이므로, [n+1: k]를 계산하기 위한 항의 총 개수는 [n: k-1]을 계산하기 위한 총 개수와 [n: k]를 계산하기 위한 항의 총 개수에다가 이 둘을 더하기 위한 항 1을 더한 수가 된다.
       그런데 [n: k-1]을 계산하기 위한 항의 개수는 가정에 의해서 2[n: k-1] -1이고, [n: k]를 계산하기 위한 항의 개수는 가정에 의해서 2[n: k] - 1이다.
  

동적계획식 알고리즘 설계전략

1. Establish a recursive property (재귀 관계식을 정립):

• 2차원 배열 B를 만들고, 각 B[i][j]에는 [i: j]값을 저장하도록 하면, 그 값은 다음과 같은 관계식으로 계산할 수 있다.
  

2. Solve an instance of the problem in a bottom-up fashion:
   • [n: k]를 구하기 위해서는 다음과 같이 B[0][0]부터 시작하여 위에서 아래로 재귀 관계식을 적용하여 배열을 채워 나가면 된다.
     결국 값은 B[n][k]에 저장된다.
     

• 문제: 이항계수를 계산한다.
  • 입력: 음수가 아닌 정수 n 과 k, 여기서 k <= n
  • 출력: bin, [n: k]

int bin2(int n, int k) {
  index i, j;
  int B[0..n][0..k];
  for(i = 0; i <= n; i++)
    for(j = 0; j <= minimum(i,k); j++)
      if(j==0 || j==1) B[i][j] = 1;
      else B[i][j] = B[i-1][j-1] + B[i-1][j];
    return B[n][k];
}

동적계획 알고리즘의 분석

• 단위연산: for-j 루프 안의 문장

• 입력의 크기: n, k
  i = 0일 때 j-루프 수행 횟수 : 1
  i = 1일 때 j-루프 수행 횟수 : 2
  i = 2일 때 j-루프 수행 횟수 : 3
  ……………
  i = k-1일 때 j-루프 수행 횟수 : k
  i = k일 때 j-루프 수행 횟수 : k + 1
  i = k+1일 때 j-루프 수행 횟수 : k + 1
  ……………
  i = n일 때 j-루프 수행 횟수 : k + 1

  따라서 총 수행횟수는:
  1 + 2 + 3 + … + k + (k+1) + … + (k+1) = k(k+1)/2 + (n-k+1)(k+1) = (2n-k+2)(k+1)/2 = O(nk)

그래프

그래프 용어

• 정점(vertex, node), 이음선(edge, arc)
• 방향 그래프(directed graph, or digraph)
• 가중치(weight), 가중치 포함 그래프 (weighted graph)
• 경로(path) - 두 정점사이에 edge가 있는 정점들의 나열
• 단순경로(simple path) - 같은 정점을 두 번 지나지 않음
• 순환(cycle) - 한 정점에서 다시 그 정점으로 돌아오는 경로
• 순환그래프(cyclic graph) vs 비순환 그래프 (acyclic graph)
• 길이(length): the sum of weights on the path (weighted graph)

            the number of edges on the path (unweighted graph)
  

Shortest Path

• Shortest Path: 한 도시에서 다른 도시로 직항로가 없는 경우

             가장 빨리 갈 수 있는 항로를 찾는 문제
  

• 문제: 가중치 포함, 방향성 그래프에서 최단경로 찾기

• Optimization problem (최적화 문제)의 정의

  • 주어진 문제에 대하여 하나 이상의 많은 해답 후보가 존재할 때, 이와 연관된 값이 최소 또는 최대인 해답(optimal solution)을 찾아야 하는 문제
  • 에너지 최소화 문제라고도 함.

• shortest Path는 Optimization problem에 속함

Brute-force algorithm(무작정 알고리즘)

• 한 정점에서 다른 정점으로의 모든 경로의 길이를 구한 뒤, 그들 중에서 최소길이를 찾는다.

동적계획식 설계전략 - 자료구조

• 그래프의 인접행렬(adjacent matrix)식 표현: W

동적계획식 설계절차

1. Establish a recursive property

   • D(k-1)을 가지고 D(k)를 계산할 수 있는 재귀 관계식을 정립
     • D(k)[i][j] = minimum(D(k-1)[i][j], D(k-1)[i][k] + D(k-1)[k][j])
   • 경우 1: {v1, v2,…, vk}의 정점들 만을 통해서 vi에서 vj로 가는 최단 경로가 vk를 거치지 않는 경우,

         보기: D(5)[1][3] = D(4)[1][3] = 3
     

   • 경우 2: {v1, v2,…, vk}의 정점들 만을 통해서 vi에서 vj로 가는 최단 경로가 vk를 거치는 경우,

         보기: D(2)[5][3] = D(1)[5][2] + D(1)[2][3] = 4 + 3 = 7
         보기: D(2)[5][4]
     

2. 상향식으로 k=1부터 n까지 다음과 같이 이 과정을 반복하여 해를 구한다.
   D(0), D(1),……,D(n)

Floyd’s Algorithm I

• 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 계산

void floyd(int n, const number W[][], number D[][]) {
  int i, j, k;
  D = W;
  for(k=1; k <= n; k++)
    for(i=1; i <= n; i++) 
      for(j=1; j <= n; j++)
        D[i][j] = minimum(D[i][j], D[i][k]+D[k][j]);
}

Floyd’s Algorithm II

• 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 계산, 각각의 최단경로를 구하라.

void floyd2(int n, const number W[][], number D[][], index P[][]) {
  index i, j, k;
  for(i=1; i <= n; i++)
    for(j=1; j <= n; j++)
      P[i][j] = 0;
  D = W;
  for(k=1; k <= n; k++) 
    for(i=1; i <= n; i++) 
      for(j=1; j <= n; j++)
        if(D[i][k] + D[k][j] < D[i][j]) {
          P[i][j] = k;
          D[i][j] = D[i][k] + D[k][j];
        }
}

최단경로의 출력

void path(index q,r) {
  if(P[q][r] != 0) {
    path(q, P[q][r]);
    count << "v" << P[q][r];
    path(P[q][r], r);
  }
}

최적의 원칙

• 어떤문제의 입력에 대한 최적해가 그 입력을 나누어 쪼갠 여러 부분에 대한 최적 해를 항상 포함하고 있으면 그 문제는 최적의 원칙(the principle of optimality)이 적용된다 라고 한다.

Optimal Binary Search Trees

• definition
  • binary search tree
    • Ordered set
    • Each node contain one key
    • The keys in the left subtree are less than or equal to the key in that tree
  • Depth - number of edges from the root
  • balanced - if the depth of the 2 subtrees of every node never different by more than 1
  • optimal - the average time it takes to locate a key is minimized

void optsearchtree(int n, const float p[], float& minavg, index R[][]) {
  index i, j, k, diagonal;
  float A[1...n+1][0..n];
  for(i=1; i<=n; i++) {
    A[i][i-1] = 0; A[i][i] = p[i]; R[i][i] = i; R[i][i-1] = 0;
    A[n+1][n] = 0; R[n+1][n] = 0;
    for(diagonal=1; diagonal <= n-1; diagonal++)
      for(i=1; i<=n-diagonal; i++) {
        j = i + diagonal;
        A[i][j] = minimum(A[i][k-1] + A[k+1][j]) + 
        R[i][j] = a value of k that gave the minimum;
      }
      minavg = A[1][n];
  }
}

The Traveling Salesperson Problem

• Problem Definition

  • Determine a shortest route that starts at the salesperson’s home city, visits each of the cities once, and ends up at the home city

• Adjacent matrix W
  

  • V = set of all the vertices
  • A = a subset of V
  • D[vi][A] = length of a shortest path from vi to v1

            passing through each vertex in A exactly once
    

• Length of an optimal tour = minimum(W[1][j] + D[vj][V - {v1, vj}])

```C
void travel(int n, const number W[][], index P[][], number& minlength) {
index i, j, k;
number D[1..n][subset of V-{v1}];
for(i=2; i<=n; i++)
D[i][0] = W[i][1];

for(k=1; k<=n-2; k++)
for(all subsets A V-{v1} containing k vertices)
for(i such that i!= 1 and vi is not in A) {
D[i][A] = min(j:vj A)(W[i][j]+D[j][A-{vj}]);
P[i][A] = value of j that gave the minimum;
}
D[1][V-{v1}] = min(2<=j<=n)(W[1][j] + D[j][A-{v1,vj}]);
P[1][V-{v1}] = value of j that gave the minimum;
minlength = D[1][V-{v1}]
}