Ich habe eine Frage zum Strahlsuchalgorithmus .
Nehmen wir zum Beispiel n = 2 (die Anzahl der Knoten, die wir von jedem Knoten aus expandieren). Also haben wir am Anfang nur die Wurzel, mit 2 Knoten, die wir daraus erweitern. Von diesen zwei Knoten erweitern wir zwei weitere. Also, im Moment haben wir 4 Blätter. Wir werden so weitermachen, bis wir die Antwort finden.
Funktioniert die Balkensuche? Erweitert es nur n = 2 von jedem Knoten oder behält es 2 Blattknoten zu allen Zeiten?
Ich dachte immer, dass n = 2 bedeutet, dass wir höchstens 2 aktive Knoten von jedem Knoten haben sollten, nicht zwei für den gesamten Baum.
Es gibt ein Strahlsuchbeispiel auf dieser Site . Ich habe Probleme, es zu verstehen. Ich verstehe den ersten Teil
%Vor% Wir verwerfen Zerind weil n = 2 . Aber ich verstehe den zweiten Teil nicht: warum wird Timisoara weggeworfen? Sollten wir nicht auch die Knoten von Timisoara sehen und dann entscheiden, welche Knoten verworfen werden? Vielleicht hat Timisoara bessere Knotenpunkte als Sibiu?
Sofern Sie nicht auf eine Variante verweisen, die nicht der Konsens Strahlsuche ist, nein.
In Beam-Search ist die Anzahl der Knoten, die Sie kennen, begrenzt - und NICHT die Anzahl der Knoten, die Sie von jedem Knoten aus folgen.
Das bedeutet, dass wenn n=2 ist, dein Strahl maximal die Größe 2 hat - zu jeder Zeit, also beginnst du von einem Knoten, dann entdeckst du alle Knoten, die von ihm erreichbar sind, verwirfst sie aber alle zwei und beende Schritt 1 mit 2 Knoten.
In Schritt 2 haben Sie zwei Knoten, und Sie erweitern beide, und verwerfen alle Knoten erneut - mit Ausnahme von genau 2 Knoten (insgesamt, nicht von jedem!).
In den nächsten Schritten - in ähnlicher Weise werden Sie nach jedem Schritt 2 Knoten behalten.
Die Auswahl des zu behaltenden Knotens erfolgt normalerweise durch eine heuristische Funktion, die auswertet, welcher Knoten dem Ziel am nächsten ist.
Beachten Sie, dass die Strahlsuche nicht abgeschlossen ist (findet eine Lösung, falls eine existiert) oder optimal (findet die beste Lösung), und die beste Möglichkeit, sie zu sehen, ist, dass%% co_de im Grunde auf Best-first-search .