Beschränkte Tiefensuche

Beschränkte Tiefensuche (englisch 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.

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 wobei für die Anzahl der Knoten und 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