Poda (computação)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes confiáveis e independentes (desde dezembro de 2010). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

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.