Die durchschnittliche oder maximale Anzahl von Kindknoten, die aus einem Suchknoten während Beweis- oder Modellsuche expandiert werden; gemessen pro Entscheidungsstufe oder als allgemeine Verzweigungsbasis des Suchbaums.

Prinzip

Der Verzweigungsfaktor bestimmt die exponentielle Wachstumsrate eines Suchbaums: wenn jeder Knoten b Kinder hat, wächst die Baumgröße ungefähr wie b^d für Tiefe d; die Reduktion von b ist entscheidend für Effizienz.

Demonstration

Eine DPLL-ähnliche Suche, die eine Variable auf wahr oder falsch setzt, hat einen Verzweigungsfaktor von bis zu 2 pro Entscheidung; eine Heuristik, die oft Unit-Propagation erzeugt, reduziert den durchschnittlichen Faktor effektiv unter 2.

Fehlanwendung

Den Verzweigungsfaktor als instanzintrinsische Konstante unabhängig vom gewählten Algorithmus oder Heuristik zu behandeln, ignoriert, dass der Verzweigung stark von Variablenordnung, Propagation und Pruning-Strategien abhängt.

Konsequenz

Ein niedrigerer durchschnittlicher Verzweigungsfaktor verringert den Suchaufwand dramatisch und kann exponentielle Suchen in praktisch lösbare Instanzen verwandeln, indem die effektive Basis der Exponentialfunktion gesenkt wird.

Umkehrung

Ein hoher Verzweigungsfaktor (viele Kinder pro Knoten) kennzeichnet eine breite statt tiefe Suche; einige Algorithmen tauschen breiteren Verzweigung gegen geringere Tiefe mit unterschiedlichen Komplexitätsauswirkungen ein.

Abgrenzung

Gilt für verzweigende Suchprozesse; schließt Maße für nicht-verzweigende Inferenzsysteme (rein lineare Transformationspipelines) aus und hängt vom Algorithmus, nicht nur von der Instanz, ab.

Semantische Spannung

Spannung mit Backdoor-Setgröße und Klauselbreite: Ein kleiner Backdoor kann nach Belegungen zu niedrigem Verzweigen führen, während breite Klauseln das Verzweigen erhöhen können, sofern Propagation dem nicht entgegenwirkt.

Synthese

Der Verzweigungsfaktor ist das lokale Ausbreitungsmaß von Suchverfahren, das zusammen mit der Suchtiefe die kombinatorische Explosion von Knoten steuert; es ist algorithmus- und instanzabhängig und zentral für Laufzeitabschätzungen.