Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Programação Dinâmica: Árvore de busca binária ótima

+2 votos
52 visitas
perguntada Jun 20 em Ciência da Computação por Adriana Molinari (111 pontos)  

Este problema foi tirado do livro \(\textit{Dynamic programming: A computational tool}\) - Art Lew e Holger Mauch (2007). Trata-se do problema da seção 2.6, \(\textit{Optimal Binary Search Tree Problem}\)

Dados alguns itens de dados e a probabilidade com que esses itens são acessados, crie uma árvore de busca binária de modo que o custo de buscar tais itens seja mínimo.

Compartilhe

1 Resposta

+2 votos
respondida Jun 20 por Adriana Molinari (111 pontos)  
editado Jun 21 por Adriana Molinari

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 ]]

comentou Jul 10 por Pablo Castro (286 pontos)  
Ótima solução. O seu código está claro e replicável. Só percebi que ao escrever o código você montou a matriz árvore com as as raízes das árvores binárias ótimas. Seria interessante imprimir a matriz no final do exercício, assim ficaria mais claro visualizar que a raiz da árvore ótima é dada pelo item D e corresponde ao índice 3.
...