Poda (computação)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde dezembro de 2010).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

Na ciência da computação, poda (em inglês: pruning) é a remoção de partes de uma árvore de decisão ou de neurônios de uma rede neural. Isso pode ocorrer porque não há significativa contribuição para a precisão ou interpretabilidade da árvore, reduzindo-se a complexidade da árvore e aumentando-se a sua generalização.

Poda alfa-beta[editar | editar código-fonte]

Uma ilustração da Poda Alfa Beta.

A poda alfa-beta (ou poda α-β) é uma variação do algoritmo minimax que visa reduzir o número de nós que são avaliados na árvore de busca. É uma busca adversarista comumente utilizada na implementação de jogadores automáticos em jogos com dois jogadores (Jogo da Velha, Xadrez, Go, etc.). Ele pára completamente de avaliar um movimento quando ele encontra, de maneira comprovada, um movimento cujo valor associado seja pior do que um movimento previamente examinado. Sendo assim, os movimentos posteriores não necessitam ser avaliados.

A poda alfa beta não altera o resultado final da avaliação de uma sub-árvore e a sua vantagem está no fato de que, em árvores de busca com um fator de ramificação muito grande, a utilização de memória será significativamente reduzida.

Exemplo[editar | editar código-fonte]

O exemplo abaixo demonstra, de uma forma simples, o princípio matemático presente no funcionamento da poda α-β.


\begin{align}
 \mathbf{minimax} & = \max \left\{
                        \min \left\{ 5,10,20 \right\},
                        \min \left\{ 2,x,y   \right\},
                        \min \left\{ 15,7,2  \right\}
                      \right\} \\
                  & = \max \left\{
                        5,
                        z,
                        2
                      \right\} \mbox{ com }z\leq 2\\
                  & = 5 \\
\end{align}

Note que, independente do valor de x e y o resultado da equação é o mesmo.


Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.