branching factor

Angol

Főnév

branching factor (tsz. branching factors)

(informatika, mesterséges intelligencia) A branching factor (magyarul: elágazási tényező) egy keresési fában vagy gráfban azt jelöli, hogy egy csomópontból átlagosan hány közvetlen gyermekcsomópontba lehet továbblépni. Ez egy fontos fogalom a mesterséges intelligencia és az algoritmuselmélet területén, különösen a keresési algoritmusok elemzésénél.

📌 Definíció

A branching factor:

Az egyes állapotokhoz (csomópontokhoz) kapcsolódó lehetséges következő lépések számának átlaga egy keresési térben.

Jelölés:

Általában: ${\textstyle b}$
Ha az érték fix: uniform branching factor
Ha változó: átlagos vagy maximális branching factor

📐 Példa

Tegyük fel, hogy egy játékfa minden csomópontjából pontosan 3 további lépés (gyermek) lehetséges.

➡️ Ilyenkor: branching factor = 3

Ha nem mindenhol ugyanannyi:

gyökérnek 2 gyermeke van
egy másik csomópontnak 4 gyermeke
egy harmadiknak 1

➡️ Akkor az átlagos branching factor: ${\textstyle (2+4+1)/3=2.33}$

🧠 Jelentősége a keresési algoritmusoknál

A keresési algoritmusok idő- és térbeli komplexitását gyakran a branching factor határozza meg.

Példa: mélységi keresés (DFS) és szélességi keresés (BFS)

Általános időkomplexitás: ${\textstyle O(b^{d})}$ ${\textstyle O(b^{d})}$ , ahol
- ${\textstyle b}$ = branching factor
- ${\textstyle d}$ = megoldás mélysége

Ez azt jelenti, hogy ha pl. ${\textstyle b=10}$ és ${\textstyle d=4}$ , akkor akár 10,000 állapotot is meg kell vizsgálni.

🕹 Kiemelt alkalmazási területek

Terület	Használat
🎮 Játék AI	Például sakkban: ${\textstyle b\approx 35}$ , Go-ban: ${\textstyle b>200}$
🔍 Állapottér-keresés	Pl. 8 királynő probléma, útkeresés
🤖 Tervezés (planning)	Lehetséges műveletek száma minden lépésnél
🧠 Mesterséges intelligencia	Heurisztikus keresés hatékonyságát befolyásolja
📊 Adatstruktúrák	Pl. B-fa, ahol a branching factor határozza meg a fa magasságát

🧩 TL;DR

A branching factor megmutatja, hogy egy csomópontból hány irányba lehet továbblépni. Nagy elágazási tényező mellett a keresési tér gyorsan robban, így az algoritmusok idő- és memóriaigénye exponenciálisan nőhet.

További információk

branching factor - Szótár.net (en-hu)
branching factor - Sztaki (en-hu)
branching factor - Merriam–Webster
branching factor - Cambridge
branching factor - WordNet
branching factor - Яндекс (en-ru)
branching factor - Google (en-hu)
branching factor - Wikidata
branching factor - Wikipédia (angol)