Grundsätzliches Prinzip

Backtracking arbeitet grundsätzlich nach dem Trial-and Error printzip. Es wird also so lange nach einer Lösung gesucht, bis sie gefunden wird. Wenn abzusehen ist, dass der aktuelle Lösungsweg nicht zur Lösung führen wird, wird ein Schritt zurück gegangen und nach einer alterantiven Lösung gesucht. Am einfachsten werden Backtracking Algorithmen rekursiv implementiert, wie man später noch im meinem Beispiel sehen wird.

Beispiel Ariadnefaden

Hierbei wird versucht den weg durch ein Labyrinth zu finden, ohne das Labyrinth zu kennen. ( Sonnst wäre das ganze ja auch ohne Witz und man nähme einfach A* Oder ähnliches. ) Man kann dabei seinen gegangnen weg markieren.

Implementierung des Ariadnefaden

Gegeben ist ein 2-dimensionalen array wo, die Wände mit einem # als char gekennzeichnet werden. Der erfolgreiche weg wird mit O und nicht erfolgreicher weg mit b markiert. Das Ziel steht drin mit Z

public boolean suche(int x, int y)
{
    // Ziel gefunden
    if(feld[x][y] == 'Z')
        return true;
    // Aktuelle Position markieren
    feld[x][y] = 'O';

    // Probieren, ob der weg nach links der richtige ist
    if((x>0 && feld[x-1][y] == ' ') || (x>0 && feld[x-1][y] == 'Z'))
    {
        boolean l = suche(x-1, y); //true, wenn Ziel gefunden
        if(l) return true;
    }
    //Probieren, ob der weg nach rechts der richtige ist
    if((x<breite && feld[x+1][y] == ' ') || (x<breite && feld[x+1][y] == 'Z'))
    {
        boolean r = suche(x+1, y); // true, wenn Ziel gefunden
        if(r) return true;
    }
    // Probieren, ob der weg nach oben der richtige ist
    if((y>0 && feld[x][y-1] == ' ') || (y>0 && feld[x][y-1] == 'Z'))
    {
        boolean o = suche(x, y-1); // true, wenn Ziel gefunden
        if(o) return true;
    }
    // Probieren, ob der weg nach unten der richtige ist
    if((y<hoehe && feld[x][y+1] == ' ') || (y<hoehe && feld[x][y+1] == 'Z'))
    {
        boolean u = suche(x, y+1); // true, wenn Ziel gefunden
        if(u) return true;
    }
    // Wenn bis jetzt noch nicht returnt, ist der weg der falsche
    // Als falsch markieren und als falschen weg returenen
    feld[x][y] = 'b';
    return false;
}

Die gelben wege waren Erfolgslos, der Grüne, führt zum Ziel.

Andere Anwendungen von Backtracking

Backtracking oft für das Lösen von NP-vollständigen Problemen genutzt, wie beim Rucksackproblem, wo man Versucht man einen Rucksack mit einer maximalen Gewichtskapazität und objekte mit einem Gewicht und einem Nuzwert hat. Dabei versucht man die beste Kombination von Gewichten und nutzen zu bekommen. Andere Beispiele wären Das Färbeproblem oder das Damen- und Springerproblem.