## [Verzweigungsfaktor](/de/node/60898) Definition 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 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 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 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 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 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 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 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 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.