vorige nächste

Tiefensuche mit backtracking


Bei der Tiefensuche mit backtracking wird in der Regel nicht der Suchraum wirklich real erzeugt. Das liegt vorrangig einmal daran, dass die Datenstruktur bei vielen Problemen zu umfangreich wäre.

Man optimiert daher nicht nur dadurch, dass man keine Daten hält, die man nicht benötigt, sondern man erzeugt sogar nur jeweils die Daten, die man wirklich benötigt. Insbesondere bei einem Satisfizierungsproblem wird man dadurch erheblich an Rechenzeit sparen können, weil die Suche im Erfolgsfall abgebrochen werden kann, ohne dass jemals alle Knoten des Suchgraphen besucht wurden.


Aufgabe zu Daten bei der Tiefensuche

  1. Verfolgen Sie die Tiefensuche in den Daten, die auf der vorherigen Seite angegeben sind!
  2. Beschreiben Sie, welche Daten man bei der Tiefensuche jeweils halten muss!
  3. Bei der Breitensuche verfolgt man nicht die Strategie "zuerst in die Tiefe", "zuerst in die Breite". Verfolgen Sie auch die Breitensuche in den Daten, die auf der vorherigen Seite angegeben sind!
  4. Lässt sich bei der Breitensuche auch bei der Erzeugung der Daten und beim Halten der Daten sparen? (Begründen Sie Ihre Antwort!)
  5. Schreiben Sie ein Programm, das unser Problem mit Breitensuche löst!