În teoria structurii grafice și a datelor, factorul de ramificare al unui arbore este numărul de descendenți direcți la fiecare nod . Dacă această valoare nu este aceeași pentru toate nodurile, se poate calcula factorul mediu de ramificare . În teoria jocurilor, factorul de ramificare al unui joc este factorul de ramificare al arborelui jocului , adică numărul de mișcări posibile într-o poziție dată.
De exemplu, la șah , dacă un „nod” este considerat o poziție legală, factorul mediu de ramificare ar fi în jur de 35 [1] [2] . Aceasta înseamnă că, în medie, un jucător are aproximativ 35 de mișcări legale la fiecare mutare. Pentru comparație, factorul de ramificare pentru jocul Go este 250 [3] .
Factorii mari de ramificare fac ca algoritmii care urmăresc fiecare rezultat posibil de la un nod, cum ar fi forța brută , să fie mai scumpi din punct de vedere computațional datorită creșterii exponențiale a numărului de noduri, care este cunoscută sub numele de explozie combinatorie .
De exemplu, dacă factorul de ramificare este 10, atunci vor exista 10 noduri la un nivel mai jos față de poziția curentă, 10 2 (sau 100) noduri la două niveluri în jos, 10 3 (sau 1000) noduri la trei niveluri în jos și așa mai departe. Cu cât factorul de ramificare este mai mare, cu atât mai rapid are loc „explozia”. Factorul de ramificare poate fi trunchiat folosind algoritmul de reducere a redundanței .