Backtracking

Geschrieben von André Ryser.

Backtracking ist eine Art um Algorithmen zu entwerfen, die im Gegensatz zur Brute-Force Strategie, wo blind alle Möglichkeiten durchprobiert werden, schrittweise die aktuelle Teillösung weiter ausgebaut wird, bis eine Lösung für das gesamte Problem gefunden wurde. Sobald man keine Ausbaumöglichkeit mehr findet, also in einer Sackgasse gelandet ist, macht man vergangene Schritte rückgängig bis sich eine noch nicht betrachtete Variante ergibt. So findet man garantiert eine Lösung, sofern auch eine existiert, oder man weiss am Ende mit Sicherheit, dass es keine Lösung gibt. Man bezeichnet dieses Vorgehen auch als Versuch-und-Irrtum-Prinzip (trial-and-error). Was ist der Vorteil gegenüber einer Brute-Force Strategie wo wir systematisch alle Möglichkeiten durchprobieren? Indem wir die Lösung nach und nach ausbauen verringern wir die Anzahl Möglichkeiten, die wir testen müssen, was wir z.B. im nachfolgenden Beispielproblem sehen werden, einen grossen Unterschied machen kann.

Backtracking sollte nur dann in Betracht gezogen werden, wenn man vorher keine DP[link] oder Greedy-Lösung[link] gefunden hat, da die Laufzeit meistens exponentiell ist. Häufig müssen im schlechtesten Fall für eine Eingabe von N Elementen alle Teilmengen (Zweierpotenz von N, \(2^N\)) oder alle Reihenfolgen (Fakultät von N, \(N!\)) untersucht werden. Backtracking kommt also nur in Frage wenn die Eingabedaten klein sind, das heisst wenn \(n \leq 20\).

Beispielproblem

Ein klassisches Backtracking Problem ist das Damenproblem. Dabei versucht man alle Damen so auf dem Schachbrett zu positionieren, dass sie sich nicht gegenseitig bedrohen. Wir interessieren uns also für Schachbrettpositionen bei denen sich in jeder Zeile, Spalte und Diagonale maximal eine Dame befindet. Wir wollen nun wissen, wie viele solche Positionen es gibt wenn das Schachbrett \(n*n\) Felder hat.

Eine mögliche Lösung für das Damenproblem Eine mögliche Lösung für das Damenproblem

Algorithmus

Die simpelste Lösung dieses Problem anzugehen wäre, alle Möglichkeiten um die n Damen auf n Reihen zu platzieren durchzugehen. Wir können bereits etwas klever sein und die Damen nicht einfach wild auf dem Schachbrett platzieren, sondern genau eine pro Spalte. Dann haben wir n Damen und für jede Dame gibt es n Felder auf denen wir sie platzieren können, das heisst wir haben eine Laufzeit von \(n^n\), was bereits für \(n=8\) sehr gross wird (\(8^8 ~= 17\) Millionen).

Mit Backtracking finden wir eine schnellere Lösung. Indem wir die Damen nacheinander platzieren und einen Schritt zurück machen sobald sich zwei Damen bedrohen, können wir uns das überprüfen von vielen Kombination aus der vorhergehenden Lösung ersparen.

Wir benutzten den folgenden Algorithmus: 1.) Setzte die erste Dame auf das Feld ganz oben Links. 2.) Gehe zur nächsten Spalte 3.) Suche die nächste gültige Platzierung für eine Dame auf dieser Spalte. Falls eine existiert gehe zu Schritt 6. 4.) Es gibt keine gültige Platzierung für diese Dame, geh auf die vordere Spalte zurück. 5.) Gehe zu Schritt 3 6.) Platziere die Dame auf der ersten gültigen Position. 7.) Wenn es die letzte Dame war sind wir fertig, andernfalls gehe zu Schritt 2.

Nachdem wir im ersten Schritt die Dame in der ersten Spalte plaziert haben, versuchen wir der Reihe nach alle Positionen in der zweiten Spalte. Bei den ersten beiden (a) und (b) haben wir sofort eine ungültige Position. Erst auf der dritten Position finden wir eine in den ersten zwei Splaten gültige Möglichkeit und fangen wieder auf der ersten Position der dritten Spalte an (c).

Implementierung

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int n;
vector<int> board;

/* Print the current board, 1 indicates a queen */
void printBoard() {
  for(int i = 0; i < n; i++) {
    for(int k = 0; k < n; k++) {
      cout << ((k == board[i]) ? 1 : 0);
    }
    cout << "\n";
  }
}

/* check for every already placed queen if she can attack us */
bool canPlaceQueen(int queen, int row) {
  for(int k = 0; k < queen-1; k++) {
    if(board[k] == row || (abs(board[k] - row) == abs(k - (queen-1)))) // same row or diagonale
      return false;
  }
  return true;
}

void PlaceQueen(int queen) {
  for(int row = 0; row < n; row++) {
    if(canPlaceQueen(queen, row)) { // Check if the queen can be placed in this row
      board[queen-1] = row; // place the queen in this row
      if(queen == n) { // we sucessfully placed the last queen
        cout << "SUCESS: board variable cotains the solution\n";
        printBoard();
      } else {
        PlaceQueen(queen+1);
      }
    }
  }
}


int main() {
  cin >> n;

  board.resize(n);
  PlaceQueen(1); // Start with the first Queen in Row 0
}

Um zu überprüfen ob zwei Damen auf der gleichen Diagonal sind verwenden wir den Ausdruck abs(Y1 - Y2) == abs(X1 - X2))

Laufzeitanalyse

Wie wir gleich sehen werden ist die Laufzeit noch \(O(n! \cdot n^2)\), statt \(O(n^n)\) in der Brute-Force Lösung. So brauchen wir z.B für \(n=8\) statt ~17 Millionen nur noch ~40‘000 Schritte. Weshalb ist diese Lösung so viel schneller als das systematische Durchprobieren mit Brute-Force? Backtracking hat die beiden folgenden Vorteile:

  • Inkrementeller Aufbau: Die Möglichkeiten werden nicht von Null auf zusammengesetzt, sondern durch eine minimale Anpassung des Vorgängers. Diese Anpassungen können auch schnell wieder rückgängig gemacht werden falls wir in eine Sackgasse laufen.
  • Pruning: Es können ganze Klassen von ungültigen Positionen ausgelassen werden. In unserem Beispiel überspringen wir z.B in einem Schritt alle Möglichkeiten, wo in den ersten beiden Spalten beide Damen auf der ersten Zeile sind.

Um die Laufzeit zu berechnen gehen wir wie folgt vor. Die Dame in der ersten Spalte können wir auf \(n\) Zeilen setzen. Für die Dame in der zweiten Spalte haben wir nun nur noch \(n-1\) Möglichkeiten, schliesslich kann sie nicht auf der selben Zeile sein wie die erste Dame. Es gibt also \(n \cdot (n-1)\) Möglichkeiten um die ersten beiden Damen zu platzieren. Für die dritte Damen gibt es dann noch \(n-2\) Möglichkeiten da nun schon 2 Zeilen vergeben sind wenn wir die dritte Dame platzieren. Wir machen das für alle \(n\) Damen und erhalten \(n \cdot (n-1) \cdot (n-2)\cdots 2 \cdot 1 = n!\) Möglichkeiten. Für jede Möglichkeit brauchen wir \(O(n^2)\) um herauszufinden, ob sich zwei Damen bedrohen. Die Laufzeit des Algorithmus ist also \(O(n! \cdot n^2)\).