logo

TechCodeview

Backtracking-Algorithmus

Backtracking-Algorithmen sind wie Problemlösungsstrategien, die dabei helfen, verschiedene Optionen zu erkunden, um die beste Lösung zu finden. Sie arbeiten, indem sie verschiedene Wege ausprobieren, und wenn einer nicht funktioniert, gehen sie einen Schritt zurück und versuchen einen anderen, bis sie den richtigen Weg gefunden haben. Es ist, als würde man ein Puzzle lösen, indem man verschiedene Teile testet, bis sie perfekt zusammenpassen.

Zurückverfolgen

Inhaltsverzeichnis



Was ist ein Backtracking-Algorithmus?

Zurückverfolgen ist eine algorithmische Technik zur Problemlösung, bei der schrittweise durch Ausprobieren eine Lösung gefunden wird verschiedene Möglichkeiten Und Verderben sie, wenn sie zu a führen Sackgasse .

Es wird häufig in Situationen verwendet, in denen Sie mehrere Möglichkeiten zur Lösung eines Problems erkunden müssen, z. B. bei der Suche nach einem Weg in einem Labyrinth oder beim Lösen von Rätseln Sudoku . Wenn eine Sackgasse erreicht wird, kehrt der Algorithmus zum vorherigen Entscheidungspunkt zurück und erkundet einen anderen Weg, bis eine Lösung gefunden wird oder alle Möglichkeiten ausgeschöpft sind.

Wie funktioniert ein Backtracking-Algorithmus?

A Backtracking-Algorithmus funktioniert, indem es rekursiv alle möglichen Lösungen für ein Problem untersucht. Es beginnt mit der Auswahl einer ersten Lösung und untersucht dann alle möglichen Erweiterungen dieser Lösung. Wenn eine Erweiterung zu einer Lösung führt, gibt der Algorithmus diese Lösung zurück. Wenn eine Erweiterung nicht zu einer Lösung führt, kehrt der Algorithmus zur vorherigen Lösung zurück und versucht eine andere Erweiterung.

Im Folgenden finden Sie einen allgemeinen Überblick über die Funktionsweise eines Backtracking-Algorithmus:

Fragen zum Java-Interview
  1. Wählen Sie eine erste Lösung.
  2. Entdecken Sie alle möglichen Erweiterungen der aktuellen Lösung.
  3. Wenn eine Erweiterung zu einer Lösung führt, geben Sie diese Lösung zurück.
  4. Wenn eine Erweiterung nicht zu einer Lösung führt, kehren Sie zur vorherigen Lösung zurück und versuchen Sie es mit einer anderen Erweiterung.
  5. Wiederholen Sie die Schritte 2 bis 4, bis alle möglichen Lösungen untersucht wurden.

Beispiel eines Backtracking-Algorithmus

Beispiel: Den kürzesten Weg durch ein Labyrinth finden

Eingang: Ein Labyrinth, dargestellt als 2D-Array, wobei 0 stellt einen offenen Raum dar und 1 stellt eine Wand dar.

Algorithmus:

  1. Beginnen Sie am Ausgangspunkt.
  2. Versuchen Sie, sich in jede der vier möglichen Richtungen (oben, unten, links, rechts) in diese Richtung zu bewegen.
  3. Wenn die Bewegung in diese Richtung zum Endpunkt führt, kehren Sie auf dem eingeschlagenen Weg zurück.
  4. Wenn die Bewegung in diese Richtung nicht zum Endpunkt führt, gehen Sie zur vorherigen Position zurück und versuchen Sie es mit einer anderen Richtung.
  5. Wiederholen Sie die Schritte 2–4, bis der Endpunkt erreicht ist oder alle möglichen Pfade erkundet wurden.

Wann sollte ein Backtracking-Algorithmus verwendet werden?

Backtracking-Algorithmen eignen sich am besten zur Lösung von Problemen mit den folgenden Merkmalen:

  • Es gibt mehrere mögliche Lösungen für das Problem.
  • Das Problem kann in kleinere Teilprobleme zerlegt werden.
  • Die Teilprobleme können unabhängig voneinander gelöst werden.

Anwendungen des Backtracking-Algorithmus

Backtracking-Algorithmen werden in einer Vielzahl von Anwendungen eingesetzt, darunter:

  • Lösen von Rätseln (z. B. Sudoku, Kreuzworträtsel)
  • Den kürzesten Weg durch ein Labyrinth finden
  • Terminprobleme
  • Probleme bei der Ressourcenzuweisung
  • Probleme bei der Netzwerkoptimierung

Grundlagen des Backtracking-Algorithmus:

  • Unterschied zwischen Backtracking und Branch-N-Bound-Technik
  • Was ist der Unterschied zwischen Backtracking und Rekursion?

Standardprobleme beim Backtracking-Algorithmus:

  • Das Tourproblem des Ritters
  • Ratte in einem Labyrinth
  • N-Queen-Problem | Backtracking-3
  • Teilmengensummenproblem
  • m Farbproblem
  • Hamilton-Zyklus
  • Sudoku | Backtracking-7
  • Magnetpuzzle
  • Entfernen Sie ungültige Klammern
  • Ein Backtracking-Ansatz zur Generierung von n-Bit-Gray-Codes
  • Schreiben Sie ein Programm, um alle Permutationen einer bestimmten Zeichenfolge auszugeben

Einfache Probleme beim Backtracking-Algorithmus:

  • Zurückverfolgen, um alle Teilmengen zu finden
  • Überprüfen Sie, ob eine bestimmte Zeichenfolge eine Summenzeichenfolge ist
  • Zählen Sie alle möglichen Pfade zwischen zwei Eckpunkten
  • Finden Sie alle unterschiedlichen Teilmengen einer gegebenen Menge
  • Finden Sie heraus, ob es von einer Quelle einen Pfad mit einer Länge von mehr als k gibt
  • Drucken Sie alle Pfade von einer bestimmten Quelle zu einem Ziel
  • Gibt alle möglichen Zeichenfolgen aus, die durch Leerzeichen erstellt werden können

Mittlere Probleme beim Backtracking-Algorithmus:

  • Tauziehen
  • 8-Königinnen-Problem
  • Kombinationssumme
  • Warnsdorffs Algorithmus für das Knight-Tour-Problem
  • Finden Sie Wege von der Eckzelle zur mittleren Zelle im Labyrinth
  • Finden Sie die maximal mögliche Anzahl, indem Sie höchstens K Swaps durchführen
  • Ratte in einem Labyrinth mit mehreren Stufen oder Sprüngen
  • N-Königin im O(n)-Raum

Schwierige Probleme beim Backtracking-Algorithmus:

  • Kraftsatz in lexikographischer Reihenfolge
  • Wortumbruchproblem mit Backtracking
  • Aufteilung einer Menge in K Teilmengen mit gleicher Summe
  • Längstmögliche Route in einer Matrix mit Hürden
  • Finden Sie den kürzesten sicheren Weg auf einem Weg mit Landminen
  • Gibt alle palindromischen Partitionen einer Zeichenfolge aus
  • Drucken aller Lösungen im N-Queen-Problem
  • Geben Sie alle längsten gemeinsamen Teilsequenzen in lexikografischer Reihenfolge aus

Quicklinks:

  • Lernen Sie Datenstruktur und Algorithmen | DSA-Tutorial
  • Die 20 häufigsten Interviewfragen zum Backtracking-Algorithmus
  • „Videos“ zum Thema Backtracking