Factor de ramificació

Erro al crear miniatura:

Un Arbre roig-negre en factor de ramificació 2.

En l'àmbit de la computació, arbres (Estructura de senyes) i teoria de jocs, es denomina factor de ramificació al número de nodos fills en cada nodo. Si este valor no és uniforme, es pot calcular el factor de ramificació mig.

Per eixemple, en escacs, si es considera un "nodo" com una posició vàlida, el factor de ramificació mig és aproximadament 35. Açò significa que, de mija, un jugador pot realisar al voltant de 35 moviments vàlits en cada tanda.

Factors de ramificació alts fan que els algoritmes que evaluen totes les branques de tots els nodos, com els de busca per força bruta, siguen més costosos computacionalment parlant pel creiximent exponencial del número de nodos, donant lloc a una explosió combinatòria.

Per eixemple, si el factor de ramificació és 10, hi haurà 10 nodos en el següent nivell a la posició actual, 10² (o 100) nodos dos nivells per davall, 10³ (o 1000) nodos tres nivells per davall, i aixina successivament. Quant major és el factor de ramificació, més ràpidament ocorre esta "explosió". El factor de ramificació pot ser reduït per mig d'algoritmes de poda.