Considere um conjunto de \(n\) itens \(X = {x_0,...,x_{n-1}}\), sendo que a probabilidade de acessar o item \(x_i\) é dada por \(p(x_i)\). A tarefa de construir uma árvore de busca binária ótima (ABBO) consiste em construir uma árvore de custo mínimo, sendo que o custo da árvore é dado por:
\[\sum^{n-1}_{i=0}(p_{x_i}level(x_i)) \]
Onde \(level(x_i)\) indica a profundidade do nó correspondente ao item \(x_i\).
A equação de programação dinâmica deste problema pode ser expressa da seguinte maneira:
\[f(i,j) = \begin{cases} \min_{k\epsilon (i,..,j)} \{f(i, k − 1) + f(k + 1, j)\} + \sum_{l=i}^{j}p_l\
& \quad \text{if } i \leq \text{j}\\
p_i & \quad \text{if } i = \text{j}
\end{cases}\]
Uma propriedade interessante de uma ABBO é que suas subárvores da esquerda e da direita também são ótimas. Portanto, para resolver o problema, precisamos apenas determinar a raiz da ABBO. Neste caso, o objetivo é encontrar \(f(0, n-1)\).
Ó código abaixo nos retorna o custo mínimo e a raiz da árvore de busca binária ótima.
A primeira função definida abaixo e dada por \(soma(prob, i, j)\) nos retorna \(\sum_{l=i}^{j}p_l\).
def soma(prob, i, j):
s = 0
for k in range(i, j + 1):
s = s + prob[k]
return s
Já a segunda função nos retornará o custo mínimo e a raiz da ABBO, além da matriz com os resultados da programação dinâmica.
import numpy as np
import sys
def ABBO(itens, prob):
n = len(itens)
custo = [[0 for a in range(n)]
for b in range(n)]
arvore = [[0 for a in range(n)]
for b in range(n)]
for i in range(n):
custo[i][i] = prob[i]
arvore[i][i] = i
for l in range(2, n + 1):
for i in range(n - l + 2):
j = i + l - 1
if i >= n or j >= n:
break
custo[i][j] = sys.maxsize
for r in range(i, j + 1):
c = soma(prob, i, j)
if (r > i):
c = c + custo[i][r - 1]
arvore[i][j] = r-1
if (r < j):
c = c + custo[r + 1][j]
arvore[i][j] = r+1
if (c < custo[i][j]):
custo[i][j] = c
arvore[i][j] = r
raiz = int(arvore[0][n - 1])
item = itens[raiz]
print('O custo mínimo da ABBO é', round(custo[0][n - 1], 2), 'e sua raiz é', arvore[0][n-1],',
o que corresponde ao item', item)
print(np.around(np.array(custo), decimals=2))
O exemplo apresentado no livro considera o seguinte conjunto de dados:
\(itens = A, B, C, D, E \\
prob = 0.25, 0.05, 0.2, 0.4, 0.1\)
Abaixo, segue a saída do código apresentado para este exemplo.
O custo mínimo da ABBO é 1.9 e sua raiz é 3 , o que corresponde ao item D.
[[0.25 0.35 0.8 1.65 1.9 ]
[0. 0.05 0.3 0.95 1.15]
[0. 0. 0.2 0.8 1. ]
[0. 0. 0. 0.4 0.6 ]
[0. 0. 0. 0. 0.1 ]]