Backtracking

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Backtracking arbeitet nach dem Prinzip der Tiefensuche

Der Begriff Rücksetzverfahren oder englisch Backtracking (engl. Rückverfolgung) bezeichnet eine Problemlösungsmethode innerhalb der Algorithmik.

Backtracking geht nach dem Versuch-und-Irrtum-Prinzip (trial and error) vor, d.h. es wird versucht, eine erreichte Teillösung schrittweise zu einer Gesamtlösung auszubauen. Wenn absehbar ist, dass eine Teillösung nicht zu einer endgültigen Lösung führen kann, wird der letzte Schritt bzw. die letzten Schritte zurückgenommen, und es werden stattdessen alternative Wege probiert. Auf diese Weise ist sichergestellt, dass alle in Frage kommenden Lösungswege ausprobiert werden können. Mit Backtracking-Algorithmen wird eine vorhandene Lösung entweder gefunden (unter Umständen nach sehr langer Laufzeit), oder es kann definitiv ausgesagt werden, dass keine Lösung existiert. Backtracking wird meistens am einfachsten rekursiv implementiert und ist ein prototypischer Anwendungsfall von Rekursion.

[Bearbeiten] Allgemeiner Algorithmus

 Funktion FindeLoesung (Stufe, Vektor)
 1. wiederhole, solange es noch neue Teil-Lösungsschritte gibt:
     a) wähle einen neuen Teil-Lösungsschritt;
     b) falls Wahl gültig ist:
            I) erweitere Vektor um Wahl;
           II) falls Vektor vollständig ist, return true; // Lösung gefunden!
               sonst: 
                 falls (FindeLoesung(Stufe+1, Vektor)) return true; // Lösung!
                 sonst mache Wahl rückgängig;   // Sackgasse (Backtracking)!
 2. Gibt es keinen neuen Teil-Lösungsschritt: return false // Keine Lösung!

[Bearbeiten] Zeitkomplexität

Bei der Tiefensuche werden bei maximal $z$ möglichen Verzweigungen von jeder Teillösung aus und einem Lösungsbaum mit maximaler Tiefe von $N$ im schlechtesten Fall $1 + z + z 2 + z 3 + ... + z N$ Knoten erweitert.

Die Tiefensuche und somit auch Backtracking haben im schlechtesten Fall mit $O (z N)$ eine exponentielle Laufzeit. Bei großer Suchtiefe n und Verzweigungsgrad $z > 1$ dauert die Suche somit oft sehr lange. Daher ist das Backtracking primär für Probleme mit einem kleinen Lösungsbaum geeignet.

Es gibt jedoch Methoden, mit welchen die Zeitkomplexität eines Backtracking-Algorithmus verringert werden kann. Diese sind u.a.:

Heuristiken
Akzeptanz von Näherungslösungen & Fehlertoleranz
Durchschnittliche Eingabemenge

[Bearbeiten] Beispiele

Bekannte Probleme, die sich mit Backtracking lösen lassen, sind u.a.:

[Bearbeiten] Damenproblem

Gegeben ist ein Schachbrett mit n*n Feldern (je n Spalten und Reihen). Man positioniere nun n Damen so, dass sie sich nicht gegenseitig schlagen können.

[Bearbeiten] Springerproblem

Gegeben ist ein „Schachbrett“ mit $m\times n$ Feldern. Ein Springer kann von einer bestimmten Position aus $N = 8$ verschiedene Sprünge ausführen, falls diese nicht über den Rand des Brettes hinausführen. Gesucht ist ein Weg, bei dem alle Felder genau einmal besucht werden (Springerweg). Mit Hilfe von Backtracking können alle möglichen Wege systematisch durchprobiert werden. Ein Zug ist dabei gültig, wenn das neue Feld innerhalb des Spielfeldes liegt und noch unbesucht ist. Es gibt jedoch weitaus effizientere Verfahren für die Lösung dieses Problems. Siehe Programmbeispiel (Java-Applet) weiter unten.

[Bearbeiten] Rucksackproblem

Gegeben ist ein Rucksack mit der Tragfähigkeit $B$ . Weiterhin sind $N$ Gegenstände mit Werten und Gewichten gegeben. Nun sollen Gegenstände so ausgewählt werden, die in der Summe einen maximalen Wert ergeben, aber deren Gesamtgewicht die Tragfähigkeit des Rucksacks nicht überschreitet.

[Bearbeiten] Färbeproblem

Gegeben ist eine Landkarte mit $B$ Ländern, welche mit $N$ verschiedenen Farben eingefärbt werden sollen. Gesucht ist eine Farbkombination, bei welcher alle Länder, die eine gemeinsame Grenze besitzen, unterschiedlich eingefärbt sind.

[Bearbeiten] Lösungen des Solitär-Brettspiels

Die Lösungen des bekannten alten Brettspiels können gut mit Backtracking ermittelt werden. Zu Beginn stehen 32 Steine (Stifte oder Kugeln) auf dem Brett; davon werden in 31 Zügen je einer entfernt, indem man ihn mit einem anderen Stein überspringt.

[Bearbeiten] Wegsuche von A nach B in einem Graph

Backtracking wird auch eingesetzt für die Wegsuche von A nach B in einem Graph, z.B. für die Suche nach Verbindungen in einem Fahrplan oder zum bestimmen einer Route in einem Routenplaner oder eines Weges durch ein Labyrinth.

[Bearbeiten] PROLOG

Automatisches Backtracking ist fester Bestandteil der Programmiersprache PROLOG und der PROLOG-Systeme.

[Bearbeiten] Programmbeispiel

Das folgende Java Applet berechnet alle Lösungen des Springerproblems (siehe oben) durch Backtracking: (Da es zur Lösung des Springerproblems viel effizientere Verfahren gibt, ist es zwar nicht das optimale Anwendungsbeispiel für Backtracking; das folgende Programm ist jedoch zur Veranschaulichung der Funktionsweise des Backtracking geeignet.)

/*    Rekursives Backtracking: Weg des Springers
 *    über alle Felder eines mxn "Schachbrettes"
 *    mit gegebener Anfangsposition (x0|y0)
 *    vgl. N.Wirth (1979): Algorithmen und Datenstrukturen.
 *    Stuttgart: Teubner. 2.Aufl., S. 191 - 198
 */

import java.awt.*;
import java.applet.*;

public class Springer extends Applet {
    private final int m=4, n=5;    // Größe des Feldes mxn
    private final int mn=m*n;
    // Die Arrays a und b enthalten die acht möglichen Springerzüge
    // in x- bzw. y-Richtung, *relativ* zur jeweiligen Ausgangsposition:
    private final static int[]  a = { +1, +2, +2, +1, -1, -2, -2, -1 },
                                b = { -2, -1, +1, +2, +2, +1, -1, -2 };
    private int[][] h;    // Weg des Springers auf dem Brett
    private long anzLoesungen = 0;
    private StringBuffer sb = null;
    private TextArea ta = null;

    public void init() {
        anzLoesungen = 0;
        sb = new StringBuffer();
        ta = new TextArea();   add(ta);   ta.setEditable(false);
        h  = new int[m][n];
        for (int i=0; i<m; i++) for (int j=0; j<n; j++) h[i][j]=0;
        int x0=0, y0=0;        // Startposition des Springers
        h[x0][y0]=1;

        tryWBT ( 2, x0, y0 );  // rekursives Backtracking starten
        ta.setText(sb.toString());
    }

    public void paint(Graphics g) { }

    private void tryWBT ( int zugNr, int x, int y ) {
    // = tryWithBackTracking
        for (int k=0; k<8; k++) {
            int u=x+a[k], v=y+b[k];
            // Zug prüfen:
            if ( u>=0 && u<m && v>=0 && v<n && h[u][v]==0) {
                h[u][v] = zugNr;    // Zug ausführen!
                if (zugNr<mn) tryWBT ( zugNr+1, u, v );    // Rekursion!
                else gefunden();    // Lösung vollständig!
                h[u][v] = 0;        // Zug rückgängig machen = Backtracking!
            }
        }
    }

    private void gefunden() {
        anzLoesungen++;    // Lösungen zählen
        sb.append ("Nr. "+anzLoesungen+":\n");
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++)
                sb.append("\t"+h[i][j]);
            sb.append("\n");
        }
    }
}

[Bearbeiten] Literatur

Robert Sedgewick: Algorithmen, Pearson Studium, 2. Aufl. 2002 ISBN 3827370329
Niklaus Wirth: Algorithmen und Datenstrukturen Stuttgart: Teubner, 3. überarb. Aufl. 1983 ISBN 3519022508