I graf- og datastrukturteori er forgreningsfaktoren for et træ antallet af direkte efterkommere ved hver knude . Hvis denne værdi ikke er den samme for alle noder, kan den gennemsnitlige forgreningsfaktor beregnes . I spilteorien er forgreningsfaktoren for et spil spiltræets forgreningsfaktor , det vil sige antallet af mulige træk i en given position.
For eksempel, i skak , hvis en "knude" betragtes som en juridisk position, vil den gennemsnitlige forgreningsfaktor være omkring 35 [1] [2] . Det betyder, at en spiller i gennemsnit har omkring 35 lovlige træk på hvert træk. Til sammenligning er forgreningsfaktoren for spillet Go 250 [3] .
Høje forgreningsfaktorer gør algoritmer, der følger ethvert muligt udfald fra en knude, såsom brute force , beregningsmæssigt dyrere på grund af den eksponentielle vækst i antallet af knudepunkter, som er kendt som en kombinatorisk eksplosion .
For eksempel, hvis forgreningsfaktoren er 10, så vil der være 10 noder et niveau ned fra den aktuelle position, 10 2 (eller 100) noder to niveauer ned, 10 3 (eller 1000) noder tre niveauer ned, og så videre. Jo højere forgreningsfaktoren er, jo hurtigere sker "eksplosionen". Forgreningsfaktoren kan afkortes ved hjælp af redundansreduktionsalgoritmen .