NP(Nondeterministic Polynomial) 문제
비결정적 다항식 시간 알고리즘을 가지는 문제
Optimal Binary Search Tree (이진 탐색 트리)
집합 S에 대한 이진탐색트리 T는 각 정점 v에 대해 레이블 값 l(v)∈S이고, 다음과 같은 조건을 만족할 때이다.
1) 정점 v의 왼쪽 부분트리에 있는 각 정점 u에 대해,
l(u) <= l(v);
2) 정점 v의 오른쪽 부분트리에 있는 각 정점 u에 대해,
l(u) >= l(v);
3) 집합 S에 있는 각 원소 a에 대해,
l(v) = a인 정점 v는 유일하게 하나 존재한다.
Procedure Search(T, x)
if x < l(root of T), then Search(leftsubtree of T, x)
if x > l(root of T), then Search(rightsubtree of T, x)
if x = l(root of T), then return
- S = {a1, a2, ..., an} 여기서, a1 < a2 < a3...이라 가정함
- P(i): 원소 ai∈S가 탐색되는 확률
(노드 안에 있는 수 ai가 탐색되는 빈도수, 높을 수록 많이 검색한다는 뜻이니까 빈도수가 높은 노드가 깊으면 검색 평균을 냈을 때 비효율적임. / 같은 확률(빈도수)이면 상관없지만, 그렇지 않은 이진트리도 볼 것이다) - Q(i): 원소 x∉S가 탐색되는 확률 (여기서, ai < x < a(i+1), 0<=i<=n)
(노드 안에 가지고 있지 않은 수 x를 검색할 확률(빈도수))
-> n개의 id로 만들어지는 binary search tree는 n개의 internal node와 n+1개의 external node를 가짐
-> Optimal Binary Search Tree는 위 식 (2)가 최소가 되는 이진탐색트리이다.
n개의 id로 만들어지는 binary search tree는 n개의 internal node(a1,a2,...)와 n+1개의 external node(E0, E1,...)를 가진다.
Optimal Binary Search Tree(최적이진탐색트리) 문제에 dynamic programming 방법을 적용하려면, 트리 형성시 관점을 sequence of decision 결과로 트리를 봐야하며, principle of optiality를 만족하는 지를 봐야한다.
if, ak가 루트노드라면,
위의 그림과 같이 왼쪽에는 k보다 작은 수의 노드들이 있어야한다. (ex. a(k-2), a(k-1), ...)
COST 계산
if 루트노드 = ak라면,
- Tij = optimal binary tree containing Ei + a(i+1) + E(i+1) + ... + aj + Ej
- C(i, j) = Tij의 cost
- R(i, j) = Tij의 root
- w(i, j) = Q(i) + (P(i+1) + Q(i+1)) + ... + (P(j) + Q(j))
COST(T) = P(k) + COST(L) + COST(R) + W(0,K-1) + W(K,n)
= COST(L) + COST(R) + W(0,n))
일반화하면,
C(i, j) = min{C(i, k-1) + C(k, j) + w(i, j)} (단, i+1 <= k <= j)
Time Complexity: O(n^3)
//4장 END.
