WikiDer > Verzweigungsfaktor

Vertakkingsfactor
EIN rot-schwarzer Baum mit Verzweigungsfaktor 2.

In dem Informatik und Spieltheorie ist der Verzweigungsfaktor von a Baumstruktur die Anzahl der Kinder von a Taste. Wenn diese Zahl nicht für alle Kinder gleich ist, kann ein durchschnittlicher Verzweigungsfaktor berechnet werden.

In zum Beispiel Schach[1] hat einen Knoten im Spielbaum zur Hälfte des Spiels ein durchschnittlicher Verzweigungsfaktor von 35[2]. Jeder Knoten im Spielbaum repräsentiert einen gültigen Zustand des Schachbretts und von jedem Knoten kann der Spieler durchschnittlich 35 gültige Züge machen.

Eine erschöpfende Suche des Spielbaums mit rohe Gewalt ist oft nicht möglich, da der (durchschnittliche) Verzweigungsfaktor zunimmt. Die Anzahl der Knoten wächst exponentiell (ein kombinatorische Explosion) mit jeder Schicht des Baums. Wenn der Verzweigungsfaktor 10 ist, dann ist der Wurzel 10 Kinder, von denen jedes auch 10 Kinder hat (insgesamt 102 = 100 Knoten) mit wieder 10 Kindern (103 = 1000 Knoten) und so weiter. Ganz allgemein gibt es einen Baum mit Tiefe d und Verzweigungsfaktor b von bd Knoten.

Die Folgen dieser kombinatorischen Explosion können begrenzt werden, indem man den Baum in einer bestimmten Tiefe schneidet und nicht tiefer in den Baum hineinschaut. Eine andere Möglichkeit besteht darin, Teile des Baumes wegzuschneiden, die bekanntermaßen nicht mehr relevant sind, zum Beispiel mit Alpha-Beta-Beschneidung ("Beschneiden" ist "Beschneiden").