Was ist der Unterschied zwischen Backtracking und Tiefensuche?

Was ist der Unterschied zwischen Backtracking und Tiefensuche?

Backtracking ist ein allgemeinerer Algorithmus.

Die Tiefensuche ist eine spezielle Form des Zurückverfolgens im Zusammenhang mit der Suche nach Baumstrukturen. Aus Wikipedia:

Man beginnt an der Wurzel (wählt einen Knoten als Wurzel im Diagrammfall aus) und erkundet so weit wie möglich entlang jedes Zweigs, bevor man zurückverfolgt.

Es verwendet Backtracking als Teil seiner Arbeit mit einem Baum, ist jedoch auf eine Baumstruktur beschränkt.

Backtracking kann jedoch für jede Art von Struktur verwendet werden, bei der Teile der Domäne entfernt werden können - unabhängig davon, ob es sich um einen logischen Baum handelt oder nicht. Das Wiki-Beispiel verwendet ein Schachbrett und ein bestimmtes Problem. Sie können sich einen bestimmten Zug ansehen und ihn beseitigen und dann zum nächsten möglichen Zug zurückkehren, ihn beseitigen usw.

Ich denke, diese Antwort auf eine andere verwandte Frage bietet mehr Einblicke.

Für mich besteht der Unterschied zwischen Backtracking und DFS darin, dass Backtracking einen impliziten Baum behandelt und DFS einen expliziten Baum behandelt. Das scheint trivial, aber es bedeutet viel. Wenn der Suchraum eines Problems durch Zurückverfolgen besucht wird, wird der implizite Baum in der Mitte durchlaufen und beschnitten. Für DFS ist der Baum / Graph, mit dem es sich befasst, explizit konstruiert und inakzeptable Fälle wurden bereits weggeworfen, dh beschnitten, bevor eine Suche durchgeführt wird.

Backtracking ist also DFS für impliziten Baum, während DFS Backbacking ohne Bereinigung ist.

Backtracking wird normalerweise als DFS plus Suchbereinigung implementiert. Sie durchlaufen den Suchraumbaum in der Tiefe und konstruieren dabei Teillösungen. Brute-Force-DFS kann alle Suchergebnisse erstellen, auch diejenigen, die praktisch keinen Sinn ergeben. Dies kann auch sehr ineffizient sein, um alle Lösungen (n! Oder 2 ^ n) zu konstruieren. In der Realität müssen Sie also bei der DFS auch Teillösungen beschneiden, die im Kontext der eigentlichen Aufgabe keinen Sinn ergeben, und sich auf die Teillösungen konzentrieren, die zu gültigen optimalen Lösungen führen können. Dies ist die eigentliche Backtracking-Technik - Sie verwerfen Teillösungen so früh wie möglich, treten einen Schritt zurück und versuchen, das lokale Optimum wieder zu finden.

Nichts hört auf, den Suchraumbaum mit BFS zu durchlaufen und dabei eine Backtracking-Strategie auszuführen. In der Praxis ist dies jedoch nicht sinnvoll, da Sie den Suchstatus Schicht für Schicht in der Warteschlange speichern müssten und die Baumbreite exponentiell zur Höhe wächst. Wir würden also sehr schnell viel Platz verschwenden. Deshalb werden Bäume normalerweise mit DFS durchquert. In diesem Fall wird der Suchstatus im Stapel gespeichert (Aufrufstapel oder explizite Struktur) und darf die Baumhöhe nicht überschreiten.

Normalerweise ist eine Tiefensuche eine Möglichkeit, eine tatsächliche Diagramm- / Baumstruktur zu durchlaufen, um nach einem Wert zu suchen, während das Zurückverfolgen einen Problemraum durchläuft, um nach einer Lösung zu suchen. Backtracking ist ein allgemeinerer Algorithmus, der sich nicht unbedingt auf Bäume bezieht.

Ich würde sagen, DFS ist die spezielle Form des Backtracking. Backtracking ist die allgemeine Form der DFS.

Wenn wir DFS auf allgemeine Probleme ausweiten, können wir es als Backtracking bezeichnen. Wenn wir Backtracking für Baum- / Diagrammprobleme verwenden, können wir es DFS nennen.

Sie tragen die gleiche Idee in algorithmischem Aspekt.

Laut Donald Knuth ist es dasselbe. Hier ist der Link in seinem Artikel über den Dancing Links-Algorithmus, der verwendet wird, um solche "Nicht-Baum" -Probleme wie N-Königinnen und Sudoku-Löser zu lösen.

Backtracking, auch Tiefensuche genannt

Meiner Meinung nach sind die meisten Antworten entweder weitgehend ungenau und / oder ohne Verweis. Lassen Sie mich also eine sehr klare Erklärung mit einer Referenz teilen .

Erstens ist DFS ein allgemeiner Graph-Traversal- (und Such-) Algorithmus. Es kann also auf jedes Diagramm (oder sogar auf die Gesamtstruktur) angewendet werden. Baum ist eine spezielle Art von Grafik, daher funktioniert DFS auch für Baum. Hören wir im Wesentlichen auf zu sagen, dass es nur für einen Baum oder ähnliches funktioniert.

Basierend auf [1] ist Backtracking eine spezielle Art von DFS, die hauptsächlich zur Speicherplatzersparnis verwendet wird. Die Unterscheidung, die ich gleich erwähnen werde, mag verwirrend erscheinen, da wir in solchen Graph-Algorithmen so daran gewöhnt sind, Adjazenzlisten-Darstellungen zu haben und iterative Muster zu verwenden, um alle unmittelbaren Nachbarn ( für Baum sind es die unmittelbaren Kinder ) eines Knotens zu besuchen Wir ignorieren oft, dass eine schlechte Implementierung von get_all_immediate_neighbors zu einem Unterschied in der Speichernutzung des zugrunde liegenden Algorithmus führen kann.

Wenn ein Graphknoten den Verzweigungsfaktor b und den Durchmesser h hat ( für einen Baum ist dies die Baumhöhe ), ist der Speicherbedarf groß-O (bh) , wenn wir alle unmittelbaren Nachbarn bei jedem Schritt des Besuchs eines Knotens speichern . Wenn wir jedoch jeweils nur einen (unmittelbaren) Nachbarn nehmen und erweitern, verringert sich die Speicherkomplexität auf Big-O (h) . Während die erstere Art der Implementierung als DFS bezeichnet wird , wird die letztere Art als Backtracking bezeichnet .

Jetzt sehen Sie, wenn Sie mit Hochsprachen arbeiten, verwenden Sie höchstwahrscheinlich tatsächlich Backtracking als DFS. Darüber hinaus kann es sehr speicherintensiv sein, die besuchten Knoten für einen sehr großen Problemsatz zu verfolgen. Forderung nach einem sorgfältigen Entwurf von get_all_immediate_neighbors (oder nach Algorithmen, mit denen ein Knoten erneut besucht werden kann, ohne in eine Endlosschleife zu geraten ).

[1] Stuart Russell und Peter Norvig, Künstliche Intelligenz: Ein moderner Ansatz, 3. Aufl

Die Tiefe zuerst ist ein Algorithmus zum Durchlaufen oder Durchsuchen eines Baums. Siehe hier . Backtracking ist ein viel weiter gefasster Begriff, der überall dort verwendet wird, wo ein Lösungskandidat gebildet und später durch Backtracking in einen früheren Zustand verworfen wird. Siehe hier . Die Tiefensuche verwendet Backtracking, um zuerst einen Zweig zu durchsuchen (Lösungskandidat) und, falls dies nicht erfolgreich ist, den anderen Zweig zu durchsuchen.

DFS beschreibt die Art und Weise, wie Sie ein Diagramm untersuchen oder durchlaufen möchten. Es konzentriert sich auf das Konzept, bei der Wahl so tief wie möglich zu gehen.

Während Backtracking normalerweise über DFS implementiert wird, konzentriert es sich mehr auf das Konzept, vielversprechende Suchunterräume so früh wie möglich zu beschneiden.

Bei einer Tiefensuche beginnen Sie an der Wurzel des Baums und erkunden dann so weit wie möglich entlang jedes Zweigs. Anschließend kehren Sie zu jedem nachfolgenden übergeordneten Knoten zurück und durchlaufen dessen untergeordnete Knoten

Backtracking ist ein allgemeiner Begriff für das Beginnen am Ende eines Ziels und das schrittweise Zurückbewegen, um schrittweise eine Lösung zu finden.

IMO, auf einem bestimmten Knoten des Backtrackings versuchen Sie zunächst, die Tiefe in jedes seiner untergeordneten Knoten zu vertiefen. Bevor Sie jedoch in einen der untergeordneten Knoten verzweigen, müssen Sie den Status des vorherigen Kindes "auslöschen" (dieser Schritt entspricht dem Zurück zum übergeordneten Knoten gehen). Mit anderen Worten, jeder Geschwisterzustand sollte sich nicht gegenseitig beeinflussen.

Im Gegensatz dazu haben Sie während eines normalen DFS-Algorithmus normalerweise diese Einschränkung nicht. Sie müssen den vorherigen Geschwisterstatus nicht löschen (zurückverfolgen), um den nächsten Geschwisterknoten zu erstellen.

Idee - Beginnen Sie an einem beliebigen Punkt und prüfen Sie, ob es sich um den gewünschten Endpunkt handelt. Wenn ja, haben wir eine Lösung gefunden, die zu allen nächstmöglichen Positionen führt. Wenn wir nicht weiter gehen können, kehren Sie zur vorherigen Position zurück und suchen Sie nach anderen Alternativen, die diesen Strom markieren Der Weg führt uns nicht zur Lösung.

Jetzt sind Backtracking und DFS zwei verschiedene Namen für dieselbe Idee, die auf zwei verschiedene abstrakte Datentypen angewendet werden.

Wenn die Idee auf die Matrixdatenstruktur angewendet wird, nennen wir sie Backtracking.

Wenn dieselbe Idee auf einen Baum oder ein Diagramm angewendet wird, nennen wir sie DFS.

Das Klischee hier ist, dass eine Matrix in einen Graphen konvertiert werden könnte und ein Graph in eine Matrix transformiert werden könnte. Wir wenden die Idee also tatsächlich an. Wenn in einem Diagramm, dann nennen wir es DFS und wenn in einer Matrix, dann nennen wir es Backtracking.

Die Idee in beiden Algorithmen ist dieselbe.

Backtracking ist nur eine Tiefensuche mit bestimmten Beendigungsbedingungen.

Gehen Sie durch ein Labyrinth, in dem Sie für jeden Schritt, den Sie treffen, einen Aufruf an den Aufrufstapel vornehmen (der Ihre erste Tiefensuche durchführt). Wenn Sie das Ende erreichen, können Sie Ihren Pfad zurückgeben. Wenn Sie jedoch eine Sackgasse erreichen, möchten Sie aus einer bestimmten Entscheidung zurückkehren, im Wesentlichen aus einer Funktion in Ihrem Aufrufstapel.

Wenn ich also an Backtracking denke, ist mir das wichtig

1. Zustand
2. Entscheidungen
3. Basisfälle (Kündigungsbedingungen)

Ich erkläre es in meinem Video zum Backtracking hier .

Eine Analyse des Backtracking-Codes finden Sie unten. In diesem Backtracking-Code möchte ich alle Kombinationen, die zu einer bestimmten Summe oder einem bestimmten Ziel führen. Daher habe ich drei Entscheidungen, die meinen Anrufstapel anrufen. Bei jeder Entscheidung kann ich entweder eine Nummer als Teil meines Pfades auswählen, um die Zielnummer zu erreichen, diese Nummer überspringen oder sie auswählen und erneut auswählen. Und wenn ich dann eine Kündigungsbedingung erreiche, ist mein Rückverfolgungsschritt nur die Rückkehr . Die Rückgabe ist der Rückverfolgungsschritt, da dieser Aufruf auf dem Aufrufstapel beendet wird.

class Solution:    

"""

Approach: Backtracking 

State
    -candidates 
    -index 
    -target 

Decisions
    -pick one --> call func changing state: index + 1, target - candidates[index], path + [candidates[index]]
    -pick one again --> call func changing state: index, target - candidates[index], path + [candidates[index]]
    -skip one --> call func changing state: index + 1, target, path

Base Cases (Termination Conditions)
    -if target == 0 and path not in ret
        append path to ret
    -if target < 0: 
        return # backtrack 

"""

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    """
    @desc find all unique combos summing to target
    @args
        @arg1 candidates, list of ints
        @arg2 target, an int
    @ret ret, list of lists 
    """
    if not candidates or min(candidates) > target: return []

    ret = []
    self.dfs(candidates, 0, target, [], ret)
    return ret 

def dfs(self, nums, index, target, path, ret):
    if target == 0 and path not in ret: 
        ret.append(path)
        return #backtracking 
    elif target < 0 or index >= len(nums): 
        return #backtracking 


    # for i in range(index, len(nums)): 
    #     self.dfs(nums, i, target-nums[i], path+[nums[i]], ret)

    pick_one = self.dfs(nums, index + 1, target - nums[index], path + [nums[index]], ret)
    pick_one_again = self.dfs(nums, index, target - nums[index], path + [nums[index]], ret)
    skip_one = self.dfs(nums, index + 1, target, path, ret)