Tip:
Highlight text to annotate it
X
Dies sind die Antworten.
Breitensuche, wie der Name schon sagt, erweitert Knoten in dieser Reihenfolge.
1 - 2 - 3 - 4 - 5 - 6 - 7.
Sie durchsucht eine Ebene nach der anderen, in die Breite.
Ist das optimal?
Nun, es wird immer erst der kürzere Pfad erweitert,
daher wird die Suche, wo auch immer das Ziel steckt, dieses finden, ohne
längere Pfade zu untersuchen. Sie ist also optimal.
Kostensuche, hier wird erst der Pfad mit Länge 0 durchsucht,
dann der Pfad mit der Länge 2.
Jetzt gibt es Pfade mit den Längen 4 und 5,
Pfade mit den Längen 6 und 7 und schlussendlich einen Pfad der Länge 8.
Wir wir schon gesehen haben, findet diese Suche garantiert den billigsten Pfad,
wenn wir annehmen, alle individuellen Schrittkosten seien nicht negativ.
Die Tiefensuche geht zuerst so tief wir sie kann,
also zuerst 1 - 2 -3, einen Schritt zurück, 4,
zwei *** zurück, 5 - 6 - 7.
Sie sehen, diese Suche findet nicht unbedingt den kürzesten aller Pfade.
Sagen wir das Ziel läge an den Positionen 5 und 3.
Die Suche fände den längeren Pfad zu Position 3 und damit das Ziel,
nicht aber das Ziel in Position 5.
Sie ist also nicht optimal.