D120.de/forum

Ist die iterative Tiefensuche wirklich optimal, wie im Kapitel "Uninformed Search" auf Seite 54 behauptet wird? Das Argument in den Folien besagt JA, denn die Lösung wird in der minimalen Tiefe gefunden. Das leuchtet ein. Aber wer sagt mir denn, dass in der gleichen Tiefe nicht noch eine bessere Lösung zu finden ist?
Im Grunde genommen sind es doch die gleichen Argumente dagegen wie bei der DFS, nur dass man bis zu einem bestimmten Level denkt.

Dreamdancer hat geschrieben:Aber wer sagt mir denn, dass in der gleichen Tiefe nicht noch eine bessere Lösung zu finden ist?

Iterative Tiefensuche geht davon aus, daß die Kosten eines Knotens gleich der Tiefe eines Knotens sind. Dann sind aber alle Lösungen in der gleichen Tiefe gleich gut, also können wir einfach die erste verwenden, die wir auffinden.

Wenn die Kosten irgendwie anders definiert sind, ist iterative Tiefensuche natürlich nicht optimal, denn es könnte sich ja irgendwo tief unten im Suchbaum eine bessere Lösung verstecken.

Wenn die Kosten irgendwie anders definiert sind, ist iterative Tiefensuche natürlich nicht optimal, denn es könnte sich ja irgendwo tief unten im Suchbaum eine bessere Lösung verstecken.

Oder man baut im zugrunde liegenden Depth-Limited-Search-Algorithmus das Tiefenmaß eben so um, dass die Kosten des Knotens verwendet werden. Solange die Kosten nur diskrete Werte annehmen, kann man dann auch DLS anwenden

Rodent Bait hat geschrieben:

Wenn die Kosten irgendwie anders definiert sind, ist iterative Tiefensuche natürlich nicht optimal, denn es könnte sich ja irgendwo tief unten im Suchbaum eine bessere Lösung verstecken.

Oder man baut im zugrunde liegenden Depth-Limited-Search-Algorithmus das Tiefenmaß eben so um, dass die Kosten des Knotens verwendet werden. Solange die Kosten nur diskrete Werte annehmen, kann man dann auch DLS anwenden

Selbst wenn die Kosten beliebige Werte annehmen, kann man eine Abart des Iterative Deepening verwenden.

Russel, Norvig hat geschrieben:The idea is to use increasing limits of path cost. If a node is generated whose path cost exceeds the current limit, it is immediately discarded. For each new iteration, the limit is set to the lowest path of any node discarded in the previous iteration. (AIMA, exercise 3.11)

Für gleichmäßig verteilte Kostenwerte ist das natürlich nicht effizient, denn es muß für jeden Knoten eine neue DFS gestartet werden. Für "fast diskrete" Kostenwerte könnte es aber eine gute Idee sein.

Tillmann hat geschrieben: Iterative Tiefensuche geht davon aus, daß die Kosten eines Knotens gleich der

Ich wusste garnicht, dass die iterative Tiefensuche als Bedingung hat, dass die Kosten immer 1 oder alle gleich sind. Für mich ist sie nur das Vorgehen, eben das iterative an der Tiefensuche
Wenn man davon ausgeht, ist sie natürlich optimal, da sie ja eine der optimalen Lösungen findet.

Trotzdem: Im Falle von variierenden Kosten ist sie nicht besser als normale DFS. Sollte man vielleicht erwähnen, denn wie wir wissen, ist alles eine Frage der Modellierung, so auch mein Baum

Dreamdancer hat geschrieben:Ich wusste garnicht, dass die iterative Tiefensuche als Bedingung hat, dass die Kosten immer 1 oder alle gleich sind. Für mich ist sie nur das Vorgehen, eben das iterative an der Tiefensuche

Naja, sagen wir mal, iterative Tiefensuche (IDS) hat als Optimalitätsbedingung, daß die Kosten alle gleich sind. Und warum sollte man einen nicht optimalen Algorithmus verwenden?

(Ok, könnte schon Sinn machen, zum Beispiel, wenn er fast optimal ist. Wenn etwa die Kosten also zwischen 0.9 und 1.1 liegen, könnte man sich entscheiden, iterative Tiefensuche zu verwenden und den möglichen Abstand der gefundenen Lösung zur besten Lösung zu akzeptieren. Siehe unten.)

Dreamdancer hat geschrieben:Trotzdem: Im Falle von variierenden Kosten ist sie nicht besser als normale DFS.

Bezüglich Optimalität: Das hängt davon ab, wie stark die Kosten variieren. Wenn sie stark variieren, kommen ähnlich schlechte Ergebnisse raus, wie bei DFS. Wenn sie nur leicht variieren, sind die Ergebnisse besser. Genauer: Wenn die Kosten in einem Intervall (a, b) liegen, haben alle Lösungen in Ebene n Gesamtkosten im Intervall (n a, n b). Im ungünstigsten Fall gibt nun die iterierte Tiefensuche die schlechtest denkbare Lösung einer Ebene n zurück. Sie hat die Gesamtkosten n b. Die beste Lösung muß dann Gesamtkosten von mindestes n a haben (denn sonst müßte sie sich auf einer Ebene < n befinden und wäre von der IDS bereits gefunden worden. Also ist gefundene Lösung um den Faktor (n b - n a) / n a = n (b - a) / a schlechter als die beste Lösung. Ergebnis: IDS liefert brauchbare Ergebnisse für niedrige Bäume und kleine Intervalle. Falls die Intervalle auf einen Punkt zusammenfallen, sind die Ergebnisse sogar optimal.

Bezüglich Terminierung: IDS terminiert für manche Suchbäume, für die DFS nicht terminiert, und umgekehrt. Beispiele: Für Bäume mit unendliche Verzweigung aber endlicher Tiefe terminiert nur DFS. Für Bäume mit endlicher Verzweigung aber unendlicher Tiefe terminiert nur IDS.

Allgemein kann man sagen, daß sich IDS bezüglich asymptotischer Laufzeitkomplexität, Terminierung und gefundener Lösung genauso verhält wie BFS, aber eine viel geringere asymptotische Speicherkomplexität hat. (Sei n die Tiefe der von IDS und BFS gefundenen Lösung. Dann muß BFS die gesamte Ebene n in der Warteschlange halten, während IDS nur einen Pfad zu n speichern muß). In der Praxis sind Terminierung und Speicherkomplexität sicher entscheidende Kriterien, ob ein Algorithmus überhaupt in die nähere Auswahl kommt. In einem zweiten Schritt kann man sich dann über die Qualität der gefundenen Lösungen Gedanken machen.