Ich benötige ein Beispiel für die Berechnung der Penetranz und Verzweigungsfaktor des Suchbaums in der heuristischen Suche im Zustandsraum. Die Definitionen lauten wie folgt. Penetranz $ P $ wird durch
$ \ qquad \ displaystyle P = \ frac {L} {T} $
und Verzweigungsfaktor definiert
$ \ qquad \ displaystyle \ frac {B} {(B-1)} \ cdot (B ^ L – 1) = T $
wobei $ L $ die Länge des Pfades von der Wurzel zur Lösung und $ T $ die Gesamtzahl der erweiterten Knoten ist.
Antwort
Betrachten Sie den folgenden Suchbaum. Ihr heuristischer Suchalgorithmus startet die Suche am Wurzelknoten. Nicht erweiterte Knoten sind grau markiert.
Aus irgendeinem Grund wird die Heuristik zum Teilbaum ganz links geführt. Tatsächlich befindet sich der Zielknoten im Teilbaum ganz rechts und ist grün markiert.
Knoten mit erweitert wurden sind rot markiert. Nachdem sich der ansprechende Teilbaum ganz links als Sackgasse herausgestellt hat, wird die Heuristik nun glücklicherweise direkt zum Ziel geführt. Ausgehend von der Situation in der vorherigen Abbildung werden wir insgesamt drei neue Knoten erweitern, bevor wir zum Ziel gelangen.
Aus der obigen Abbildung geht hervor, dass der Pfad zum Ziel $ 3 $ beträgt. Es gibt $ 17 $ erweiterte Knoten. Daher ist die Penetranz ist $ 3/17 \ ca. 0,43 $.
Der Verzweigungsfaktor ist die maximale Anzahl Beispielsweise beträgt der Verzweigungsfaktor eines Binärbaums $ 2 $, da jeder Knoten höchstens zwei untergeordnete Knoten hat. Ebenso beträgt der Verzweigungsfaktor im obigen Suchbaum $ 3 $.
Was Sie scheinen nicht an dem Verzweigungsfaktor interessiert zu sein, sondern an dem effektiven Verzweigungsfaktor $ B ^ * $, der ein Weg ist um die Qualität einer Heuristik zu charakterisieren. Wenn die Gesamtzahl der erweiterten Knoten $ T $ beträgt und die Länge des Pfades zum Ziel $ L $ beträgt (dies ist allgemein bekannt a) s Tiefe ), dann ist $ B ^ * $ der Verzweigungsfaktor, den ein einheitlicher Baum der Tiefe $ L $ haben würde, um $ T + 1 $ Knoten zu enthalten. Daher ist
$$ T + 1 = 1 + B ^ * + (B ^ *) ^ 2 + \ cdots + (B ^ *) ^ L. $$
If Wenn Sie die Werte einstecken, die wir bei der Suche erhalten haben, dh $ T = 17 $ und $ L = 3 $, erhalten Sie $ B ^ * \ ca. 2.165 $. Dies ist genau der gleiche Wert, den Sie durch die Verwendung Ihrer Gleichung erhalten. Es handelt sich lediglich um eine andere Darstellung für dieselbe Sache.
Der effektive Verzweigungsfaktor kann von Fall zu Fall variieren, ist jedoch für ausreichend schwierige Probleme etwas konstant. Eine gut gestaltete Heuristik hätte einen Wert von $ B. ^ * $ in der Nähe von $ 1 $, wodurch relativ große Probleme kostengünstig gelöst werden können.
Kommentare
- Lösen Sie die Formel für $ B $ Ich frage mich, wie dieser Wert interpretiert wird. ' liegt nahe am durchschnittlichen Verzweigungsfaktor aller inneren Knoten, aber nicht gleich.
- @MAcad Tatsächlich interessiert Sie nicht der Verzweigungsfaktor, sondern der effektive Verzweigungsfaktor, der die Qualität einer Heuristik charakterisiert. I ' aktualisiert meine Antwort.
- @Juho Ich denke, wenn ich die Verzweigungsfaktorformel verwende, werde ich viele Zahlen in der LHS testen und berechnen und wie folgt mit RHS gleich prüfen: B = 1 == > 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4 ungleich T = 17, also müssen wir B = 2 == > 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15 the testen Ergebnis in der Nähe von T, damit wir B = 2.1 und so weiter testen können, bis das Ergebnis T erreicht ist !!!! Ich denke, diese Formel kann so verwendet werden :))))