Metraipolis › archive › dc_f8e8ec6a249b
Iterative Tiefensuche — Wikipedia (de)
- Source
- Wikipedia (de)
- Original
- https://de.wikipedia.org/wiki/Iterative_Tiefensuche
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-09T06:17:39.262Z
- SHA-256 of the archived text
fd7d3d9a9f1be12c2efe6f3a70be62027cf71cd3b0507b53995f2e05305ea27f- Stable URL of this page
https://metraipolis.com/documento/dc_f8e8ec6a249b
How to cite
Iterative Tiefensuche — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Iterative_Tiefensuche (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_f8e8ec6a249b (Metraipolis archive dc_f8e8ec6a249b, sha256 fd7d3d9a9f1be12c2efe6f3a70be62027cf71cd3b0507b53995f2e05305ea27f)
BibTeX
@misc{dcf8e8ec6a249b,
title = {Iterative Tiefensuche — Wikipedia (de)},
howpublished = {Wikipedia (de)},
url = {https://de.wikipedia.org/wiki/Iterative_Tiefensuche},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_f8e8ec6a249b; sha256 fd7d3d9a9f1be12c2efe6f3a70be62027cf71cd3b0507b53995f2e05305ea27f},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/Iterative_Tiefensuche. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Die iterative Tiefensuche (englisch iterative deepening depth-first search, IDDFS) ist ein Verfahren aus der Informatik zum Suchen eines Knotens in einem Graphen. Der Algorithmus kombiniert die wünschenswerten Eigenschaften von Tiefensuche (geringer Speicherverbrauch) und Breitensuche (Optimalität). Die iterative Tiefensuche ist wie die normale Tiefensuche eine uninformierte Suche. Sie funktioniert wie die Tiefensuche, vermeidet jedoch durch Begrenzung der Suchtiefe deren Nachteile bezüglich Vollständigkeit. Bei der iterativen Tiefensuche wird iterativ eine beschränkte Tiefensuche durchgeführt, und dabei das Level, bis zu welchem die Beschränkte Tiefensuche den Graphen erkundet, bei jeder Iteration um eins erhöht. Im ersten Schritt werden also alle Knoten, zu denen ein Pfad der Länge 0 führt, mittels Tiefensuche erkundet. Im nächsten Schritt werden dann alle Knoten, zu denen ein Pfad der Länge 1 führt, mittels Tiefensuche erkundet und so weiter. Hierdurch wird erreicht, dass Iterative Tiefensuche prinzipiell auf allen Graphen vollständig ist, da die Suche sich nun nicht mehr in einem endlos langen Pfad verlieren kann. Damit stellt die iterative Tiefensuche eine Kombination der Tiefen- und der Breitensuche dar. Sie hat einerseits den gleichen Speicherplatzverbrauch wie die normale Tiefensuche (im Arbeitsspeicher muss jeweils maximal ein kompletter Ast bis zur momentanen Iterationstiefe gespeichert werden), liefert aber bei monoton steigenden Pfadkosten, ebenso wie die Breitensuche, eine optimale Lösung. Da für jede neue Iteration auch der bereits durchlaufene Suchbaum komplett neu aufgebaut werden muss, ist die Laufzeit höher als bei normaler Tiefensuche. Da in einem Suchbaum aber jeweils der größte Teil der Knoten Blätter sind, ist dieser geringe Mehraufwand gegenüber den Vorteilen hinnehmbar. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in tedesco, in ordine alfabetico). Fonte: Wikipedia in tedesco, voce «Iterative Tiefensuche» — https://de.wikipedia.org/wiki/Iterative_Tiefensuche Wikidata Q1675274: «search strategy» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1675274 Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Iterative_Tiefensuche?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 255586558, consultata il 2026-11-09T06:14:05.647Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: bdef6e54a7c4acd5be881d3a6baa058d99cbad63d39af77e584f613cb26d1e0a