Fattore di diramazione

Un RB-Albero con fattore di branch di valore 2.

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. 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.

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.

Applicazioni

Il fattore di diramazione è solitamente denotato dal simbolo $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 $b^{*}$ per cui il numero reale di nodi dell'albero sia:

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

Noto $b$, con tale formula, nel caso in cui il valore del fattore di diramazione sia costante è possibile calcolare il numero di nodi dell'albero.

Collegamenti esterni

• Digrafo (matematica)
• Gerarchia