V teorii grafů a datových struktur je faktorem větvení stromu počet přímých potomků v každém uzlu . Pokud tato hodnota není pro všechny uzly stejná, lze vypočítat průměrný faktor větvení . V teorii her je faktorem větvení hry faktor větvení stromu hry , tedy počet možných tahů na dané pozici.
Například, v šachu , jestliže “uzel” je považován za legální pozici, průměrný faktor větvení by byl kolem 35 [1] [2] . To znamená, že v průměru má hráč asi 35 legálních tahů na každý tah. Pro srovnání, faktor větvení pro hru Go je 250 [3] .
Vysoké faktory větvení způsobují, že algoritmy, které sledují každý možný výsledek z uzlu, jako je hrubá síla , jsou výpočetně dražší kvůli exponenciálnímu růstu počtu uzlů, což je známé jako kombinatorická exploze .
Pokud je například faktor větvení 10, pak bude 10 uzlů o jednu úroveň níže od aktuální pozice, 10 2 (nebo 100) uzlů o dvě úrovně níže, 10 3 (nebo 1000) uzlů o tři úrovně níže a tak dále. Čím vyšší je faktor větvení, tím rychleji dojde k „výbuchu“. Faktor větvení lze zkrátit pomocí algoritmu redundance redundancy .