branching factor

branching factor (tsz. branching factors)

1. (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.

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

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}$

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

• Általános időkomplexitás: ${\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.

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

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.

• 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)