Greningsfaktor

Greningsfaktor, eller branching factor, är ett begrepp inom datavetenskap, matematik och nätverksteori som beskriver hur många omedelbara grenar eller val som står till buds från en nod i en graf, ett träd eller ett beslutsträd. I ett rotat träd motsvarar greningsfaktorn antalet barn per nod; i allmänna grafer är den lika med nodens utgående kantantal, eller ut-degree. Den genomsnittliga greningsfaktorn b anger det genomsnittliga antalet utgående grenar över de noder som ingår i analysen.

Användning: I sökalgoritmer och artificiell intelligens påverkar greningsfaktorn storleken på sökträdet. Om greningsfaktorn är konstant och djupet d, är antalet besökta noder ungefär proportionellt mot b^d. Varierande greningsfaktorer leder till icke-uniforma sökträd och kräver ofta begrepp som effektiv greningsfaktor för att beskriva den praktiska komplexiteten.

Greningsfaktor i sannolikhetsteori: Inom branching processes beskriver den förväntade avkommars antal per individ, ofta betecknat som m. En process är superkritisk om m>1, subkritisk om m<1, och kritisk om m=1. Begreppet används även inom biologi och populationsekologi för att beskriva tillväxt eller utrotning av populationer.

Exempel och nyanser: En fullständig k-ary-träd har greningsfaktorn k. I spelteori och praktiska problem varierar antalet tillgängliga drag mellan noder och över nivåer, vilket gör att en enkel uppskattning av b kan ge en grov bild men inte hela historien.

Begränsningar: Greningsfaktorn är ett förenklat mått och ensam bestämmer inte problemets komplexitet. Djup, pruning, synlighet och tidsfaktor spelar ofta lika stor eller större roll. Se även ut-degree, sökalgoritmer och branching process.