Tip:
Highlight text to annotate it
X
Wir haben uns also 2 Suchalgorithmen angesehen.
Zum einen Breitensuche, bei der wir zuerst immer
den flachsten, kürzesten Pfad erweitern.
Zweitens, "cheapest-first"-Suche (uniforme Kostensuche), bei der wir immer den Pfad
mit den niedrigsten Gesamtkosten expandieren.
Ich nutze diese Gelegenheit, einen dritten Algorithmus vorzustellen, Tiefensuche,
der in gewisser Hinsicht das Gegenteil zur Breitensuche ist.
In der Tiefensuche erweitern wir immer zuerst den längsten Pfad,
den Pfad mit den meisten Längen.
Jetzt möchte ich Sie fragen, in welcher Reihenfolge jeder dieser Knoten
in jedem dieser Bäume expandiert.
Erster, zweiter, dritter, vierter und so weiter, indem Sie eine Zahl in die Box schreiben.
Falls es Gleichstände gibt, lösen sie diese von links nach rechts auf.
Dann möchte ich, dass Sie eine weitere Frage beantworten:
Welche dieser Suchen sind optimal?
Soll heißen, findet garantiert die beste Lösung?
Für die Breitensuche hieße optimal dann, den kürzesten Pfad zu finden.
Wenn Sie glauben, dass das passiert kreuzen sie hier an.
Für die Kostensuche hieße das, den Pfad mit den niedrigsten Gesamtkosten zu finden.
Kreuzen Sie hier an, wenn sie glauben, dass sie das
garantiert schafft. Dabei seien alle Kosten positiv.
Und in der Tiefensuche bedeuted optimal dann wieder,
wie in der Breitensuche, den kürzesten Pfad in bezug auf die Anzahl der Längen.
Kreuzen Sie hier an, wenn Tiefensuche dieses Ergebnis immer liefert.