Quelltext der Seite Beschränkte Tiefensuche

'''Beschränkte Tiefensuche''' ({{enS|''depth-limited search''}}, ''DLS'') ist in der [[Informatik]] ein Verfahren zum Suchen eines [[Knoten (Graphentheorie)|Knotens]] in einem [[Graph (Graphentheorie)|Graphen]]. Der Algorithmus ist eine Abwandlung der [[Tiefensuche]]. Anwendung findet die Beschränkte Tiefensuche im Algorithmus der [[Iterative Tiefensuche|iterativen Tiefensuche]].

== Allgemeines ==
Die beschränkte Tiefensuche ist wie schon die normale Tiefensuche eine [[Suchalgorithmus#Heuristische (Informierte) Suchalgorithmen|uninformierte Suche]]. Sie funktioniert genau wie die Tiefensuche, vermeidet jedoch durch Begrenzung der Suchtiefe deren Nachteile bezüglich Vollständigkeit. Hierbei wird eine bestimmte Tiefe vorgegeben, ab der die Tiefensuche abbricht, und somit auf jeden Fall terminiert. Durch die Beschränkung der Tiefe kann sich die beschränkte Tiefensuche weder in unendlich tiefen [[Pfad (Graphentheorie)|Pfaden]] noch in [[Zyklus (Graphentheorie)|Zyklen]] verlieren. Somit kann Tiefensuche – wenn eine Lösung innerhalb der selbst vorgegebenen Tiefe liegt – vollständig werden, also diese Lösung auf jeden Fall und unabhängig von dem Aufbau des Graphen finden.

== Algorithmus (informal) ==
# Bestimme den Knoten, an dem die Suche beginnen soll, und bestimme die maximale Suchtiefe
# Prüfe, ob der aktuelle Knoten innerhalb der maximalen Suchtiefe liegt
#* Falls nein: Tue nichts
#* Falls ja:
#*# Expandiere den Knoten und speichere alle Nachfolger in einem [[Stapelspeicher|Stack]]
#*# Rufe rekursiv für jeden der Knoten des Stacks DLS auf und gehe zu Schritt 2

== Algorithmus (formal) ==
 '''DLS'''(node, goal, depth)
 {
   if (node == goal)
     return node;
   stack := expand (node)
   while (''stack is not empty'')
   {
     node' := pop(stack);
     if (node'.depth() < depth)
       '''DLS'''(node', goal, depth);
   }
 }

== Eigenschaften ==
=== Speicherplatzverbrauch ===
Da intern auf [[Tiefensuche]] zurückgegriffen wird, ist der [[Platzkomplexität|Speicherplatzbedarf]] äquivalent zu dem der normalen Tiefensuche.

=== Laufzeit ===
Da intern auf Tiefensuche zurückgegriffen wird, ist die [[Zeitkomplexität|Laufzeit]] äquivalent zu der von normaler Tiefensuche, und ist somit <math>O( \vert V \vert + \vert E \vert )</math> wobei <math> \vert V \vert </math> für die Anzahl der [[Knoten (Graphentheorie)|Knoten]] und <math> \vert E \vert </math> für die Anzahl der [[Kante (Graphentheorie)|Kanten]] im erkundeten Graph steht. Hierbei ist zu beachten, dass nicht alle Knoten und Kanten des gesamten Graphen betrachtet werden, da nur diejenigen Knoten expandiert werden, welche innerhalb der selbst vorgegebenen Tiefe liegen.

=== Vollständigkeit ===
Obwohl sich Beschränkte Tiefensuche weder in unendlichen langen Pfaden noch in Zyklen verlieren kann, ist der Algorithmus im Allgemeinen nicht vollständig. Wählt man die maximale Suchtiefe zu gering, so findet der Algorithmus eine eventuell weiter entfernt liegende Lösung nicht. Wählt man die maximale Suchtiefe jedoch tiefer als die Tiefe, auf der die Lösung liegt, so ist der Algorithmus vollständig.

=== Optimalität ===
Beschränkte Tiefensuche ist nicht optimal, da sie immer noch einem Pfad solange wie möglich in die Tiefe folgt, wodurch sie auf diesem Pfad ein Ziel finden kann, welches sehr viel teurer ist als ein alternatives Ziel auf einem anderen Pfad.

== Siehe auch ==
* [[Breitensuche]]

== Literatur ==
* [[Stuart Russell]], [[Peter Norvig]]: ''[http://aima.cs.berkeley.edu/ Artificial Intelligence: A Modern Approach]'', 2. Auflage, 2002, Prentice Hall.

[[Kategorie:Graphsuchalgorithmus]]