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