Förgreningsfaktor

Från Wikipedia
Hoppa till navigering Hoppa till sök
Förgreningsfaktor
Mått för antalet barnnoder vid varje nod i träddatastrukturer Redigera
Red-black tree example.svg
Mått Redigera
Undertyp avberäkningsbarhet
 • komplexitetsteori Redigera

Förgreningsfaktor är inom databehandling, träddatastrukturer och artificiell intelligens ett mått för antalet barnnoder vid varje nod, det vill säga utgraden. Om detta värde inte är enhetligt kan en genomsnittlig förgreningsfaktor beräknas.

Till exempel, i schack sägs den genomsnittliga förgreningsfaktorn vara ca 35. Det innebär att en spelare i genomsnitt har cirka 35 möjliga drag vid varje tur. I jämförelse är den genomsnittliga förgreningsfaktorn för spelet Go 250.

Högre förgreningsfaktorer gör algoritmer som följer varje barn vid varje nod med totalsökning beräkningsmässigt dyrare på grund av att noderna ökas exponentiellt.