Beschränkte Tiefensuche

Beschränkte Tiefensuche (engl. Depth Limited search, DLS) ist in der Informatik ein Verfahren zum Suchen eines Knotens in einem Graphen. Der Algorithmus ist eine Abwandlung der Tiefensuche. Anwendung findet die Beschränkte Tiefensuche im Algorithmus der Iterativen Tiefensuche.

Inhaltsverzeichnis

Allgemeines

Die beschränkte Tiefensuche ist wie schon die normale Tiefensuche eine 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 Pfaden noch in 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)

  1. Bestimme den Knoten, an dem die Suche beginnen soll, und bestimme die maximale Suchtiefe
  2. Prüfe, ob der aktuelle Knoten innerhalb der maximalen Suchtiefe liegt
    • Falls nein: Tue nichts
    • Falls ja:
      1. Expandiere den Knoten und speichere alle Nachfolger in einem Stack
      2. 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 Speicherplatzbedarf äquivalent zu dem der normalen Tiefensuche.

Laufzeit

Da intern auf Tiefensuche zurückgegriffen wird, ist die Laufzeit äquivalent zu der von normaler Tiefensuche, und ist somit O( \vert V \vert + \vert E \vert ) wobei  \vert V \vert für die Anzahl der Knoten und  \vert E \vert für die Anzahl der 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

Literatur


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Tiefensuche — (Depth First Search) ist in der Informatik ein Verfahren zum Suchen eines Knotens in einem Graphen. Sie zählt zu den uninformierten Suchalgorithmen. Eine Verbesserung der Tiefensuche ist die iterative Tiefensuche. Inha …   Deutsch Wikipedia

  • Iterative Tiefensuche — Die iterative Tiefensuche (engl. iterative deepening search) ist ein Begriff aus der Informatik. Sie ist ein Verfahren zum Suchen eines Knotens in einem Graphen. Der Algorithmus kombiniert die wünschenswerten Eigenschaften von Tiefensuche… …   Deutsch Wikipedia

  • Depth-First Search — Tiefensuche Tiefensuche (Depth First Search) ist in der Informatik ein Verfahren zum Suchen eines Knotens in einem Graphen. Sie zählt zu den uninformierten Suchalgorithmen. Eine Verbesserung der Tiefensuche ist die iterative Tiefensuche.… …   Deutsch Wikipedia

  • Breitendurchlauf — Breitensuche Breitensuche (Breadth First Search) ist ein Fachbegriff der Informatik, welcher ein Verfahren zum Durchsuchen bzw. Durchlaufen der Knoten eines Graphens bezeichnet. Sie zählt zu den uninformierten Suchen. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Uniforme Kostensuche — Breitensuche Breitensuche (Breadth First Search) ist ein Fachbegriff der Informatik, welcher ein Verfahren zum Durchsuchen bzw. Durchlaufen der Knoten eines Graphens bezeichnet. Sie zählt zu den uninformierten Suchen. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Breitensuche — (englisch breadth first search, BFS) ist ein Fachbegriff der Informatik, welcher ein Verfahren zum Durchsuchen bzw. Durchlaufen der Knoten eines Graphen bezeichnet. Sie zählt zu den uninformierten Suchen …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”