컴퓨터 알고리즘 2023-04-03 수업정리

Flow

• Dynamic Programming - Optimal Binary Search Trees(1)

Dynamic Programming - Optimal Binary Search Trees(1)

---

Binary Search Tree

• Binary tree의 각 노드는 하나의 key값을 포함하며, 왼쪽 subtree에 위치한 key값은 오른쪽 subtree에 위치한 key값과 비교해 같거나 작은 key값을 가진다.
• Binary Tree의 Attribute로 Depth, Balanced, Search time이 있다.
  • Depth : level이라고도 불리며 루트에서 해당 노드 까지의 경로에 위치한 노드의 수를 depth라고 한다. tree의 depth는 해당 tree에서 가장 큰 depth값을 가지는 노드의 depth이다.
  • Balanced : 모든 노드에서 두 개의 subtree의 노드 수가 1이상 차이나지 않는다면 Balanced이다.
    • BST는 Balanced일 필요는 없다.
  • Search Time : 주어진 key값을 찾을 때, 해당 key값까지 도달하기 위해 수행해야 하는 비교 연산의 횟수이다.
    • Average Search Time은 아래와 같이 나타낼 수 있다. 이때 c는 비교 연산의 횟수, p는 해당 노드가 선택될 확률(frequency)이다.$$Average\ Search\ Time\ =\ \sum_{i=1}^n c_ip_i$$
• 한 집합에 대해 Binary Search Tree는 여러 개가 존재할 수 있다. 이 중에서 Average Search Time이 가장 적은 BST를 Optimal Binary Search Tree라고 한다.
• Optimal Binary Search Tree를 찾기 위해 모든 BST에 대한 경우의 수를 따지게 된다면 이는 exponential time을 요구한다. root node를 제외한 나머지 노드의 BST 구성에 대한 경우의 수는 아래와 같다.$$O(2^{n-1})$$
• 하지만, Binary Search Tree의 특성상, 어떠한 노드에 대해 왼쪽 subtree와 오른쪽 subtree가 Optimal Binary Search Tree라면, 해당 노드를 root node로 가지는 Binary Search Tree역시 Optimal Binary Search Tree가 된다. 이러한 특성을 반영한 Recursive Equation과 Matrix를 이용하면 Dynamic Programming을 통해 Optimal Binary Search Tree를 찾을 수 있다.

Optimal Binary Search Tree

• Dynamic Programming을 적용하기 위해서는 Recursive Equation과 matrix가 필요하다. 앞서 살펴본 BST의 임의의 노드에 대한 왼쪽 서브트리와 오른쪽 서브트리가 optimal일때, 해당 노드를 루트로 가지는 BST역시 optimal이라는 특성을 반영한 Recursive Equation은 아래와 같다.
  • Recursive Equation$$A[i][j] = min_{i\le k\le j}(A[i][k-1] + A[k+1][j] + \sum_{m=i}^j p_m)\ \ (*\ A[i][i] = p_i)$$
    • 위 점화식을 풀어서 설명하면, i보다 크거나 같고, j보다 작거나 같은 수 k에 대해서 k를 루트 노드로 가지는 모든 BST에 대해서 최소 Average Search Time을 가지는 BST를 찾아 내는 과정이다.
    • k를 루트 노드로 가지는 각각의 경우에 대해, 왼쪽 서브트리의 탐색시간, 오른쪽 서브트리의 탐색시간, 루트 노드의 탐색시간을 더한 값이 해당 BST의 Average Search Time이다.
    • A[i][i]의 경우 탐색에 필요한 비교 연산 횟수가 1이다. 따라서, 해당 노드가 선택될 확률인 p에 대해서만 고려하면 된다.
  • 위의 recursive equation을 tree의 모든 노드로 확장하면 아래와 같다.$$A[1][n] = min_k(A[1][k-1] + A[k+1][n] + \sum_{m=1}^n p_m)$$
  • 결국 root가 되는 key값(k값)을 찾는 것이 optimal BST를 찾는 것과 귀결된다.
• 어떤 Data set에 대한 Optimal BST Average Search Time을 찾는 C++코드는 아래와 같다.

// 코드 구현해서 채워 넣을 것, 현재 구현한 코드에 오류 있어서 추후 업로드(2023-04-09)

다음 수업에 이어서 진행...