In informatica, strutture dati ad albero, e teoria dei giochi, il fattore di diramazione (fattore di branching) è il numero di nodi figlio per ogni nodo dell'albero. Se tale valore non è costante, di solito viene calcolato il fattore di diramazione medio.

Per esempio, negli scacchi, per un nodo (rappresentante una situazione sulla scacchiera) considerato valido, è stato calcolato che il fattore di ramificazione medio sia 35.^[1] Ciò significa che, di media, un giocatore ha a disposizione circa 35 mosse legali ad ogni turno. Nel caso invece del gioco del Go, il fattore di diramazione è 250.^[1]

Più elevato è il fattore di diramazione, più gli algoritmi che a ogni nodo seguono i cammini di tutti i figli (come ad esempio il metodo di ricerca a forza bruta) sono costosi, computazionalmente parlando, a causa della crescita esponenziale del numero di nodi.

Per esempio, se il fattore di diramazione è 10, partendo dalla radice (1 nodo), nel livello uno ci saranno 10 nodi, nel livello due 10² ( 100) nodi, 10³ (1000) nodi a livello tre e così via. Più il fattore di diramazione è elevato, prima l'esplosione combinatoria avverrà. Il fattore di diramazione può essere ridotto sfruttando degli algoritmi di pruning specifici per il problema, come ad esempio l'alfa-beta pruning.

Il fattore di diramazione è solitamente denotato dal simbolo ${\displaystyle b}$ e viene impiegato per calcolare la complessità spaziale e temporale di alcune strategie di ricerca ad albero, come la ricerca in ampiezza. Per altre strategie, come ad esempio la ricerca A*, è più utile considerate il fattore di diramazione effettivo, definito come il valore ${\displaystyle b^{*}}$ per cui il numero reale di nodi dell'albero sia:

${\displaystyle \left({\frac {b^{*d+1}-1}{b-1}}\right)}$

Noto ${\displaystyle b}$, con tale formula, nel caso in cui il valore del fattore di diramazione sia costante è possibile calcolare il numero di nodi dell'albero.^[2]

• Digrafo (matematica)
• Gerarchia

Portale Informatica

Portale Matematica