Förgreningsfaktor
Inom datoranvändning , träddatastrukturer och spelteori är förgreningsfaktorn antalet barn vid varje nod , utgraden . Om detta värde inte är enhetligt kan en genomsnittlig förgreningsfaktor beräknas.
Till exempel, i schack , om en "nod" anses vara en rättslig position, har den genomsnittliga förgreningsfaktorn sagts vara cirka 35, och en statistisk analys av över 2,5 miljoner spel visade ett genomsnitt på 31. Detta betyder att, i genomsnitt har en spelare cirka 31 till 35 lagliga drag till sitt förfogande vid varje tur. Som jämförelse är den genomsnittliga förgreningsfaktorn för spelet Go 250.
Högre förgreningsfaktorer gör algoritmer som följer varje förgrening vid varje nod, såsom uttömmande brute force-sökningar , beräkningsmässigt dyrare på grund av det exponentiellt ökande antalet noder, vilket leder till en kombinatorisk explosion .
Till exempel, om förgreningsfaktorn är 10, kommer det att finnas 10 noder en nivå ner från den aktuella positionen, 10 2 (eller 100) noder två nivåer ner, 10 3 (eller 1 000) noder tre nivåer ner, och så vidare. Ju högre förgreningsfaktor, desto snabbare sker denna "explosion". Förgreningsfaktorn kan minskas med en beskärningsalgoritm .
Den genomsnittliga förgreningsfaktorn kan snabbt beräknas som antalet icke-rotnoder (trädets storlek, minus en; eller antalet kanter) dividerat med antalet icke-lövnoder (antalet noder med barn).