Im Suchbaum unten befinden sich 11 Knoten, von denen 5 Blätter sind. Es gibt 10 Verzweigungen.
Wird der durchschnittliche Verzweigungsfaktor durch 10/6 oder 10/11 angegeben?
Werden Blätter in die Berechnung einbezogen? Intuitiv würde ich nicht denken, da wir an Knoten mit Zweigen interessiert sind. Eine von meinem Professor gegebene Definition lautete jedoch „Die durchschnittliche Anzahl der Zweige aller Knoten im Baum“, was bedeuten würde, dass Blätter enthalten sind.
Kommentare
- Gute Frage. Ich habe mir ' die Freiheit genommen, das " ai-basic " -Tag hinzuzufügen. Willkommen bei Stack: AI!
Antwort
Ich würde sagen, dass die Blätter per se
Ein solcher Knoten hat wirklich keine Kinder und es ist keine weitere Berechnung erforderlich. Anders als bei Knoten, die noch nicht erweitert wurden.
Beachten Sie, dass das Zählen der Blätter nachweislich nachweislich zu für jeden n -Knoten dich!
Antwort
Aus Wikipedia:
Beim Rechnen, bei Baumdatenstrukturen und in der Spieltheorie ist der Verzweigungsfaktor die Anzahl der Kinder an jedem Knoten , outdegree . Wenn dieser Wert nicht einheitlich ist, kann ein durchschnittlicher Verzweigungsfaktor berechnet werden.
Outdegree Bedeutung – Bei gerichteten Graphen die Anzahl der Kanten Ein Knoten wird als In-Grad des entsprechenden Knotens bezeichnet, und die Anzahl der aus einem Knoten kommenden Kanten wird als Out-Grad des entsprechenden Knotens bezeichnet.
Sie haben die outdegree Teil. In AI wir g Zeichnen Sie im Allgemeinen gerichtete Graphen von einem Zustand in einen anderen, und outdegree ist die Anzahl der Pfade, die einen bestimmten Knoten verlassen. In Ihrem Diagramm ist die Richtung nicht angegeben. Auch Ihr Diagramm ist nicht symmetrisch, aber Sie können den Verzweigungsfaktor (mit ein wenig Schwierigkeit) von nicht symmetrisch gerichteten Diagrammen wie hier herausfinden. Technisch gesehen ist Ihre Schlussfolgerung also richtig, dass Blattknoten nicht gezählt werden (vorausgesetzt, sie sind der letzte Zustand, von dem aus kein anderer Zustand erreicht werden kann – Sackgasse). Hoffe das hilft!