Fator de ramificação - Branching factor
Na computação , nas estruturas de dados em árvore e na teoria dos jogos , o fator de ramificação é o número de filhos em cada nó , o outdegree . Se este valor não for uniforme, um fator de ramificação médio pode ser calculado.
Por exemplo, no xadrez , se um "nó" é considerado uma posição legal, o fator médio de ramificação foi considerado cerca de 35, e uma análise estatística de mais de 2,5 milhões de jogos revelou uma média de 31. Isso significa que, em média, um jogador tem cerca de 31 a 35 movimentos legais à sua disposição em cada jogada. Em comparação, o fator de ramificação médio para o jogo Go é 250.
Fatores de ramificação mais altos tornam os algoritmos que seguem cada ramificação em cada nó, como pesquisas exaustivas de força bruta , computacionalmente mais caros devido ao número exponencialmente crescente de nós, levando à explosão combinatória .
Por exemplo, se o factor de ramificação é de 10, então haverá 10 nós um nível baixo a partir da posição actual, 10 2 (ou 100) nós de dois níveis para baixo, 10 3 (ou 1000) nós de três níveis para baixo, e assim por diante. Quanto mais alto o fator de ramificação, mais rápido ocorre essa "explosão". O fator de ramificação pode ser reduzido por um algoritmo de poda .
O fator de ramificação médio pode ser calculado rapidamente como o número de nós não-raiz (o tamanho da árvore, menos um; ou o número de arestas) dividido pelo número de nós não-folha (o número de nós com filhos).