Backtracking-Algorithmen: Rekursiv und Suche anhand von Beispielen erklärt

Beispiele, bei denen Backtracking zum Lösen von Rätseln oder Problemen verwendet werden kann, sind:

  1. Rätsel wie Acht-Königinnen-Rätsel, Kreuzworträtsel, verbale Arithmetik, Sudoku [Nr. 1] und Peg Solitaire.
  2. Kombinatorische Optimierungsprobleme wie das Parsen und das Rucksackproblem.
  3. Logikprogrammiersprachen wie Icon, Planner und Prolog, die intern Backtracking verwenden, um Antworten zu generieren.

Beispielproblem (The Knight's Tour Problem)

Der Ritter wird auf den ersten Block eines leeren Bretts gelegt und muss sich nach den Schachregeln jedes Feld genau einmal besuchen.

Pfad gefolgt von Knight, um alle Zellen abzudecken

Es folgt ein Schachbrett mit 8 x 8 Zellen. Zahlen in Zellen geben die Bewegungsnummer des Ritters an.

Die Tourlösung des Ritters - von Euler

Naiver Algorithmus für Knights Tour

Der naive Algorithmus besteht darin, alle Touren einzeln zu generieren und zu überprüfen, ob die generierte Tour die Einschränkungen erfüllt.

while there are untried tours { generate the next tour if this tour covers all squares { print this path; } } 

Backtracking-Algorithmus für Knights Tour

Es folgt der Backtracking-Algorithmus für Knights Tour-Problem.

If all squares are visited print the solution Else a) Add one of the next moves to solution vector and recursively check if this move leads to a solution. (A Knight can make maximum eight moves. We choose one of the 8 moves in this step). b) If the move chosen in the above step doesn't lead to a solution then remove this move from the solution vector and try other alternative moves. c) If none of the alternatives work then return false (Returning false will remove the previously added item in recursion and if false is returned by the initial call of recursion then "no solution exists" ) 

Und hier ist eine Video-Erklärung für Sie