Algorithmen für Suchbaum vs. Baum

Question

Ich möchte einen Algorithmus haben, der so schnell wie möglich eine Lösung erhält, die darin besteht, ausgehend von einem Zustand in einem Baum alle möglichen Zustände in einer Baumstruktur zu durchlaufen, Warum wäre es notwendig, zuerst einen Baum zu erstellen und ihn dann zu durchqueren, anstatt einen Baum zu erstellen, und wenn während des Erstellens eines Lösungsknotens die Erstellung gestoppt und sofort auf den Stamm zurückgesetzt wird, den Pfad zu diesem Blatt notieren ?

Gibt es grundsätzlich einen BF-Algorithmus, um eine Baumbreite zu erzeugen, anstatt zuerst einen Baum zu erstellen und ihn dann in der Breite zuerst zu durchsuchen?

Art wie die animierten Ergebnisse here:

Vielen Dank für das Lesen

Answer 1

Es gibt keinen Vorteil in einem Suchalgorithmus einen Baum und dann suchen, es zu bauen, genau wegen der Gründe, die Sie erwähnt haben. Darüber hinaus gibt es keinen Suchvorteil, der durch das Erstellen einer Baumbreite zuerst oder der Tiefe zuerst erreicht wird.

In der Regel sind bereits Bäume vorhanden und wir durchqueren sie mit dem Breadth-First-Ansatz oder dem Depth-First-Ansatz. Der Grund, warum wir einen dieser Ansätze wählen, liegt an einer Eigenschaft des Suchelements oder des Baumes.

Wenn Sie Fälle gesehen haben, in denen wir einen Baum erstellen und ihn dann durchsuchen, müssen Sie aus pädagogischen Gründen ein eigenständiges Programm schreiben, das den Baum erstellt und dann durchläuft. Dies ist vergleichbar mit dem Erstellen einer verknüpften Liste von Zahlen und dem Ausführen einer linearen Suche oder dem Erstellen eines binären Suchbaums und dem anschließenden Suchen nach einem Wert. Typischerweise neigt dieser Ansatz dazu, über die Erzeugung und Durchquerung einer in ein Programm gepackten Datenstruktur zu lehren.