Tip:
Highlight text to annotate it
X
Angesichts der Non-Optimalität der Tiefensuche,
warum würde sie irgendjemand benutzen?
Nun, die Antwort hat mit den Speichervoraussetzungen zu tun.
Hier zeige ich einen Zustandsraum
bestehend aus einem großen, oder sogar unendlichen binären Baum.
Ausgehend von Ebenen 1, 2, 3, herunter bis n,
wird der Baum größer und größer.
Bedenken wir nun die Grenze für jeden dieser Suchalgorithmen.
In der Breitensuche sieht eine Grenze, wie wir wissen, so aus,
und wenn wir auf Ebene n suchen, benötigen wir Speicherplatz von 2^n
für einen Durchlauf mittels Breitensuche.
Für die Kostensuche wird die Grenze komplizierter aussehen.
Sie wird eine Art Kostenkontur abbilden,
aber eine ähnliche Anzahl Knotenpunkte enthalten.
Doch für die Tiefensuche, wenn wir den Baum entlanggehen, suchen wir erst diesen Ast ab,
dann gehen wir wieder hoch und zu jedem Zeitpunkt wird die Grenze n Knoten enthalten,
anstatt 2^n Knoten, was eine deutliche Einsparung für die Tiefensuche darstellt.
Allerdings für den Fall, dass wir auch das erforschte Gebiet speichern
ist der Speichervorteil viel geringer.
Aber ohne die erforschte Menge hat die Tiefensuche einen Riesenvorteil
in Bezug auf den Speicherplatz.
Eine weitere Eigenschaft dieser Algorithmen
ist die sogenannte Vollständigkeit, was heißt, wenn es da ein Ziel gibt,
wird der Algorithmus es finden?
Also gehen wir von großen auf unendliche Bäume über,
und nehmen wir an, dass ein Ziel weit unten entlang des Baumes versteckt ist.
Die Frage ist nun, ist jeder dieser Algorithmen vollständig?
Das heißt, finden sie alle einen Pfad zum Ziel?
Haken sie alle Kästchen der Algorithmen ab, die Sie für in diesem Sinne vollständig halten.