Fattore di diramazione
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/220px-Red-black_tree_example.svg.png)
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 102 ( 100) nodi, 103 (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
[modifica | modifica wikitesto]Il fattore di diramazione è solitamente denotato dal simbolo 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 per cui il numero reale di nodi dell'albero sia:
Noto , con tale formula, nel caso in cui il valore del fattore di diramazione sia costante è possibile calcolare il numero di nodi dell'albero.[2]
Note
[modifica | modifica wikitesto]- ^ a b François Dominic Laramée, Chess Programming Part IV: Basic Search, su gamedev.net, GameDev.net, 6 agosto 2000. URL consultato il 1º maggio 2007.
- ^ Stuart Russell and Peter Norvig, Artificial Intelligence A Modern Approach 2nd Edition, Upper Saddle River, New Jersey, Pearson Education, 2003, ISBN 0-13-080302-2.