Iterative Vertiefung
Definition
Iterative Vertiefung wiederholt tiefenbegrenzte Tiefensuchen mit schrittweise erhöhtem Tiefenlimit.
Bei endlicher Verzweigung und einer Lösung in endlicher Tiefe findet das Verfahren eine Lösung geringster Tiefe. Bei einheitlichen positiven Schrittkosten ist diese auch kostenminimal. Der Speicherbedarf bleibt im untersuchten Baumsuchmodell gering.
Einfach erklärt
Wie einen Suchbaum erst bis Tiefe 1, dann 2, dann 3 zu durchsuchen, bis eine Lösung auftaucht.
Warum das im Alltag wichtig ist
Relevant für Such- und Planungsprobleme mit unbekannter Lösungstiefe und begrenztem Speicher.
Beispiel aus dem Mittelstand
Ein Planer sucht eine kurze Folge zulässiger Prozessschritte und erhöht die maximale Plantiefe iterativ.
Grenzen und Fallstricke
- Wiederholte Arbeit als Fehler ansehen; variable Kosten ignorieren; mit A* oder allgemeiner Iteration verwechseln.
Entstehung & Geschichte
Korf untersuchte 1985 Depth-First Iterative Deepening im Modell der Brute-force-Baumsuche und analysierte Speicherbedarf und Optimalität unter festgelegten Bedingungen.
Anwendung im Mittelstand
- Mögliche Anwendung: kleine diskrete Planungs- und Suchprobleme, besonders bei begrenztem Speicher.
Häufige Fragen
Ist IDDFS schneller als BFS?
Nicht generell; ein wichtiger Vorteil ist der geringe Speicherbedarf. Wann findet es eine kostenminimale Lösung? Bei endlicher Verzweigung, einer Lösung in endlicher Tiefe und einheitlichen positiven Schrittkosten.
Quellen
- Depth-First Iterative-Deepening · Korf (1985), Depth-First Iterative-Deepening
- Autorenarbeit · Korf (1985), Autorenarbeit
Quellenprüfung: 10./11.10.2026.
Redaktionell geprüft am: