Backtracking

nur relevant für den Leistungskurs!

Erklärvideos

• Rucksackproblem mit Backtracking lösen: Java Implementierung

Idee

Der folgende Text ist gekürzt aus der Wikipedia [1] übernommen.

Backtracking geht nach dem Versuch-und-Irrtum-Prinzip (trial and error) vor, das heißt, es wird versucht, eine erreichte Teillösung 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 beziehungsweise werden 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

Backtracking wird am einfachsten rekursiv implementiert.

Beschreibung des Algorithmus

Die folgende Beschreibung ist gekürzt und leicht verändert aus der Wikipedia [2] übernommen.

Teillösung ist zu Anfang leer.
Stufe ist 0.

Funktion FindeLoesung (Stufe, Teillösung)
 1. Abbruchbedingung: Wenn die Stufe zu groß ist
                       oder es keinen Teil-Lösungsschritt mehr gibt.   
 2. Abbruchbedingung: Wenn eine Lösung erreicht wurde.
                      Bearbeite ggf. die Lösung!   
 3. wiederhole, solange es noch neue Teil-Lösungsschritte gibt:
    a) Wähle einen neuen Teil-Lösungsschritt. 
    b) Erweitere Teillösung um Wahl.      
    c) rekursiver Aufruf: FindeLoesung(Stufe+1, Teillösung) 
    d) Mache die Erweiterung der Teillösung rückgängig 

Backtracking für kürzeste Wege auf Graphen

Um kürzeste Wege auf Graphen zu bestimmen, kann man den Backtracking-Algorithmus verwenden. Allerdings ist dieser sehr langsam; effizienter wird das Problem mit dem Dijkstra-Algorithmus gelöst.

Beispiel

Graph mit fünf Städten

Gesucht ist die kürzeste Verbindung von Frankfurt nach Dortmund

Damit man keine Möglichkeit auslässt, geht man nach einer Ordnung vor - hier bietet es sich an, die möglichen Nachbarstädte nach dem Alphabet zu betrachten.

Dann ergibt sich für das Backtracking folgende Reihenfolge:

• Frankfurt -> Kassel -> Dortmund: merken!
• Frankfurt -> Kassel -> Würzburg: Sackgasse
• Frankfurt -> Köln -> Dortmund: kürzer, also merken!
• Frankfurt -> Würzburg -> Kassel -> Dortmund: länger, also ignorieren

Backtracking-Algorithmus für den kürzesten Weg

Man braucht die folgenden Attribute:

• besterWeg: Hier wird der jeweils beste gefundene Weg gespeichert.
• besteLaenge: Die Länge von besterWeg
• aktuellerWeg: Der Weg, der gerade untersucht wird.
• aktuelleLaenge: Die Länge von aktuellerWeg

Mithilfe dieser lässt sich der Algorithmus so beschreiben:

  findeKuerzestenWegBacktracking (pNode)
    Abbruchbedingung:
      Wenn pNode das Ziel ist (d.h. der Lösungsvektor ist vollständig!)
      dann vergleiche aktuellerWeg mit besterWeg
           und aktualisiere diesen, wenn es nötig ist.
    Betrachte der Reihe nach alle Nachbarn von pNode.
    Für jeden Nachbarn wird folgendes getan:
    - den Nachbar zu aktuellerWeg hinzufügen (d.h. der Lösungsvektor wird erweitert!)
    - aktuelleLaenge entsprechend erhöhen
    - den Nachbarn markieren
    - findeKuerzstestenWegBacktracking (nachbar) aufrufen
    - die Änderungen wieder rückgängig machen (d.h. die Wahl wird rückgängig gemacht!)
      - den Nachbarn aus aktuellerWeg entfernen
      - aktuelleDistanz wieder zurücksetzen
      - die Markierung des Nachbarn entfernen

Implementierung

Die Implementierung setzt auf die Klasse Graph auf.

Damit während des Backtracking auf die wesentlichen Daten zugegriffen werden kann, werden diese in Attributen gespeichert.

Die wesentlichen Methoden sind die folgenden:

• die Rahmenmethode kuerzestenWegFinden(String pStart, String pZiel): In der Rahmenmethode wird alles für das rekursive Backtracking vorbereitet.
• die rekursive Backtracking-Methode kuerzestenWegFindenBacktracking(GraphNode pNode)

   // Attribute
   public GraphWithViewer graph;

   // Attribute fuer das Backtracking
   public ListWithViewer<Vertex> besterWeg;
   public ListWithViewer<Vertex> aktuellerWeg;
   public int besteLaenge;
   public int aktuelleLaenge;
   public Vertex start;
   public Vertex ziel;

   //Methoden

   /**
    * Kopiert den Inhalt einer Liste in eine andere Liste.
    * Der Inhalt der Ziel-Liste wird dabei ersetzt.
    * @param herkunftsListe
    * @param zielListe
    */
   private void kopiereListeIn(List herkunftsListe, List zielListe){
       // besterWeg leeren
       for(zielListe.toFirst();!zielListe.isEmpty();){
           zielListe.remove();
       }
       // aktuellerWeg in besterWeg kopieren
       for(herkunftsListe.toFirst();herkunftsListe.hasAccess();herkunftsListe.next()){
           zielListe.append(herkunftsListe.getContent());
       }
   }

   public ListWithViewer<Vertex> kuerzestenWegFinden(String pStart, String pZiel){
       graph.setAllEdgeMarks(false);
       start = graph.getVertex(pStart);
       ziel = graph.getVertex(pZiel);
       besterWeg = new ListWithViewer<>();
       aktuellerWeg = new ListWithViewer<>();
       besteLaenge = 10000000;
       aktuelleLaenge = 0;
       start.setMark(true);
       aktuellerWeg.append(start);
       kuerzestenWegFindenBacktracking(start);
       return besterWeg;
   }
 
   private void kuerzestenWegFindenBacktracking(Vertex pNode) {
       if(pNode.equals(ziel)){
           if(aktuelleLaenge < besteLaenge){
               // aktuellerWeg in besterWeg kopieren
               kopiereListeIn(aktuellerWeg,besterWeg);
               besteLaenge = aktuelleLaenge;
           }
           return;
       }
       List<Vertex> nachbarn = graph.getNeighbours(pNode);
       for(nachbarn.toFirst(); nachbarn.hasAccess(); nachbarn.next()){
           Vertex derNachbar = nachbarn.getContent();
           if(!derNachbar.isMarked()){
               derNachbar.setMark(true);
               aktuellerWeg.append(derNachbar);
               double distanz = graph.getEdge(derNachbar, pNode).getWeight();
               aktuelleLaenge += distanz;
               kuerzestenWegFindenBacktracking(derNachbar);
               aktuelleLaenge -= distanz;
               aktuellerWeg.toLast();
               aktuellerWeg.remove();
               derNachbar.setMark(false);
           }
       }
       return;
   }

Backtracking für Arrays: Magisches Quadrat

In ein magisches Quadrat werden die Zahlen von 1 bis 9 (bzw. 1 bis 16, 1 bis 25, ...) eingetragen. Die Summe muss in jeder Zeile, Spalte und Diagonale gleich sein.

Lösungen dieses Problems lassen sich gut mit Backtracking finden.

Implementierung

Die folgende Implementierung löst ein 3x3 Quadrat.

• Als Datenstruktur muss nur das Quadrat bereitgestellt werden, das ein 3x3-Array ist.
• Die Stufen des Backtracking-Verfahrens sind hier die Felder; dabei gehen die Stufen von 0 bis 8.
• Aus der Stufe kann man die Koordinaten des Feldes berechnen.
• Das eigentliche Backtracking findet in der Methode public void findeLoesung(int pStufe) statt; diese Methode wird von der Rahmenmethode public void findeLoesung() aufgerufen.

public class MagischesQuadratFertig {

   private int[][] quadrat;
  
   MagischesQuadratFertig(){
       quadrat = new int[3][3];
       initialisiere();
   }

   public void initialisiere(){
       for ( int y=0 ; y < 3 ; y++ ) {
           for ( int x=0 ; x < 3 ; x++ ) {
               quadrat[x][y] = 0;
           }
       }
   }

   public void findeLoesung(){
       findeLoesung(0);
       System.out.println("*** Loesung: ***");
       this.ausgeben();
   }
  
   //Die eigentliche Backtracking-Methode!
   public boolean findeLoesung(int pStufe){
       
       ausgeben();
      
       // Abbruch, wenn pStufe ueber das Quadrat hinausgeht.
       if(pStufe == 3*3){
           return false;
       }
      
       // aus pStufe die x-Koordinate und die y-Koordinate berechnen
       int x = pStufe % 3;
       int y = pStufe / 3;
  
       // jetzt fuer pStude alle Moeglichkeiten durchlaufen,
       // d.h. die Zahlen von 1 bis 9
       for(int i=1; i<= 3*3; i++){
           // die Zahl i an die richtige Stelle in das Quadrat eintragen
           quadrat[x][y] = i;

           // Wenn es die Zahl schon einmal gibt, dann zur naechsten Zahl weiter.
           if(esGibtDoppelte()){
               continue;
           }
 
           // wenn man ein magisches Quadrat gefunden hat, dann true zurueckgeben.
           if(magisch()){
               return true;
           }
          
           // es gibt keine Doppelten, aber das Quadrat ist (noch) nicht magisch
           // d.h. man baut die Teilloesung weiter aus.
           // Dafuer ein rekursiver Aufruf fuer die naechsthoehere Stufe.
           // Der Aufruf gibt zurueck, ob das Ausbauen der Teilloesung zum Erfolg fuehrte.
           boolean fertig = findeLoesung(pStufe + 1);
           if(fertig){
               return true;
           }
       } // end for
      
       // Auf dieser Stufe wurden alle Zahlen von 1 bis 9 durchprobiert, ohne Erfolg.
       // Man loescht die Information auf dieser Stufe...
       quadrat[x][y] = 0;
       // und gibt false zurueck
       return false;
   }
   
   public boolean esGibtDoppelte(){
       boolean[] dabei = new boolean[3*3+1];
       for ( int y=0 ; y < 3 ; y++ ) {
           for ( int x=0 ; x < 3 ; x++ ) {
               int index = quadrat[x][y];
               if(index != 0 && dabei[index]){
                   return true;
               }
               dabei[index] = true;
           }
       }
       return false;
   }

   public boolean magisch(){
       if(esGibtDoppelte()){
           return false;
       }
       // Summen testen
       int s=0, t=0;
       // 1. Diagonale
       for ( int x=0 ; x < 3 ; x++ ) s+=quadrat[x][x];
       //2. Diagonale
       for ( int x=0 ; x < 3 ; x++ ) t+=quadrat[3-x-1][x];
       if (t != s) return false;
       // Zeilen
       for ( int y=0 ; y < 3 ; y++ ) {
           int k=0;
           for ( int x=0 ; x < 3 ; x++ ) {
               k += quadrat[x][y];
           }
           if (k != s) return false;
       }

       for ( int x=0 ; x < 3 ; x++ ) {
           int k=0;
           for ( int y=0 ; y < 3 ; y++ ) {
               k += quadrat[x][y];
           }
           if (k != s) return false;
       }
       System.out.println("*** It's magic!!! ***");
       return true;
   }

   public void ausgeben(){
       for ( int y=0 ; y < 3 ; y++ ) {
           for ( int x=0 ; x < 3 ; x++ ) {
               System.out.print(quadrat[x][y]);
           }
           System.out.print(" ");
       }
       System.out.println();
   }
   
   public static void main(String[] args) {
       MagischesQuadratFertig mq = new MagischesQuadratFertig();
       mq.findeLoesung();
   }
}

Aufgabe: Backtracking für Arrays: Rucksackproblem selber programmieren

Das Rucksackproblem lässt anhand des folgenden Beispiels beschreiben:

• In einen Rucksack kann man 200kg laden (=ganz schön schwer...).
• Es gibt die folgenden Gewichte: 28, 57, 33, 18, 99, 42, 17, 52
• Welche Gewichte muss man in den Rucksack laden, damit die 200kg möglichst gut ausgenutzt, aber nicht überschritten werden?

Implementierung zum Selbermachen

Die folgende Implementierung hält neben gewichte und maxGewicht noch folgende Datenstrukturen bereit:

• boolean[] teilLoesung: In diesem Array wird festgehalten, welche der Gewichte bei der aktuell untersuchten Lösung dabei sind.
• boolean[] besteLoesung: In diesem Array wird die bisher beste Lösung festgehalten.

Diese Variablen müssen natürlich im Laufe des Backtracking immer aktualisiert werden.

Die Implementierung ist noch nicht vollständig; der Backtracking-Teil muss hier noch programmiert werden; dafür muss die Methode sucheBesteLoesung(int pStufe) ergänzt werden.

Viel Spaß beim Programmieren!

 public class Rucksackproblem {
   public int[] gewichte = {28, 57, 33, 18, 99, 42, 17, 52};
   public int maxGewicht = 200;

   public boolean[] teilLoesung = new boolean[gewichte.length]; 
   public boolean[] besteLoesung = new boolean[gewichte.length];

   public void sucheBesteLoesung(){
      //Vorbereitung
      for(int i=0; i<teilLoesung.length; i++){
          teilLoesung[i] = false;
      }
      kopiereInBesteLoesung();
      // los gehts!
      sucheBesteLoesung(0);
      System.out.println("*** Beste Loesung: ***");
      ausgeben(besteLoesung);
  }

  public void sucheBesteLoesung(int pStufe) {
      teilLoesungAusgeben();
      //TODO
  }

  public void ausgeben(boolean[] b){
      System.out.print(berechneGewicht(b)+": ");
      for(int i=0; i<b.length; i++){
          if(b[i]){
              System.out.print(gewichte[i]+",");
          }
      }
      System.out.println();
  }

  public void teilLoesungAusgeben(){
      for(int i=0; i<teilLoesung.length; i++){
          if(teilLoesung[i]){
              System.out.print("+");
          }
          else{
              System.out.print("-");
          }
      }
      System.out.println();
  }

  public void kopiereInBesteLoesung(){
      for(int i=0; i<teilLoesung.length; i++){
          besteLoesung[i] = teilLoesung[i];
      }
  }

  public int berechneGewicht(boolean[] b){
      int ergebnis = 0;
      for(int i=0; i<b.length; i++){
          if(b[i]){
              ergebnis += gewichte[i];
          }
      }
      return ergebnis;
  }

  public static void main(String[] args) {
      Rucksackproblem rp = new Rucksackproblem();
      rp.sucheBesteLoesung();
  }
}

Aufgabe: Backtracking zum Lösen von Sudokus

Wer hat nicht schon mal entnervt beim Lösen eines Sudokus den Bleistift bis auf den Stummel runtergeschrieben?!

Abhilfe schafft hier ein geeignetes Java-Programm!

Die "langweiligen" Hilfsmethoden sind unten schon programmiert - es fehlt nur noch die Methode loesenMitBacktracking(int pStufe).

Hinweise:

• Die "Teillösung" muss man nicht als Parameter der Backtracking-Methode übergeben, weil immer das Array zahlen entsprechend aktualisiert wird.

• Die "Stufe" beginnt nicht bei 0, sondern bei der Anzahl der belegten Felder. Dann kann der Backtracking-Algorithmus abbrechen, sobald man die Stufe 81 erreicht.

public class Sudoku {

   // Das "schwerste Sudoku der Welt"   
   // https://www.oe24.at/welt/Das-ist-das-schwierigste-Sudoku-der-Welt/1597831   
   int[][] zahlen = {
           {0,0,5,3,0,0,0,0,0},
           {8,0,0,0,0,0,0,2,0},
           {0,7,0,0,1,0,5,0,0},
           {4,0,0,0,0,5,3,0,0},
           {0,1,0,0,7,0,0,0,6},
           {0,0,3,2,0,0,0,8,0},
           {0,6,0,5,0,0,0,0,9},
           {0,0,4,0,0,0,0,3,0},
           {0,0,0,0,0,9,7,0,0}
   };
   
   public static void main(String[] args) {
       Sudoku s = new Sudoku();
       System.out.println("*** Aufgabe ***");
       s.ausgeben();
       int belegteFelder = s.belegteFelder();
       boolean erfolg = s.loesenMitBacktracking(belegteFelder);
       if(erfolg == true){
           System.out.println("Loesung gefunden!");
       }
       else{
           System.out.println("keine Loesung");
       }
   }
   
   public boolean loesenMitBacktracking(int pStufe){
       //TODO
       return false;
   }

   private void ausgeben() {
       String trennlinie = "+---+---+---+";
       for(int zeile = 0; zeile<9; zeile++){
           if(zeile%3 == 0){
               System.out.println(trennlinie);
           }
           for(int spalte=0; spalte<9; spalte++){
               if(spalte%3 == 0){
                   System.out.print("|");
               }
               System.out.print(zahlen[zeile][spalte]);
           }
           System.out.println("|");
       }
       System.out.println(trennlinie);
       System.out.println();
   }

   public boolean istOkZeile(int pZeilenNr){
       boolean[] verwendeteZahlen = new boolean[10];
       for(int spalte = 0; spalte<9; spalte++){
           int z= zahlen[pZeilenNr][spalte];
           if(z!=0){
               if(verwendeteZahlen[z] == true){
                   return false;
               }
               verwendeteZahlen[z] = true;
           }
       }
       return true;
   }

   public boolean istOkSpalte(int pSpaltenNr){
       boolean[] verwendeteZahlen = new boolean[10];
       for(int zeile = 0; zeile<9; zeile++){
           int z= zahlen[zeile][pSpaltenNr];
           if(z!=0){
               if(verwendeteZahlen[z] == true){
                   return false;
               }
               verwendeteZahlen[z] = true;
           }
       }
       return true;
   }
   
   /**
    * ueberprueft, ob das Quadrat ok ist,
    * in dem (pZeilenNr|pSpaltenNr) liegt.
    * @param pZeilenNr
    * @param pSpaltenNr
    * @return
    */
   public boolean istOkQuadrat(int pZeilenNr, int pSpaltenNr){
       boolean[] verwendeteZahlen = new boolean[10];
       int startZeile = pZeilenNr - pZeilenNr%3;
       int startSpalte = pSpaltenNr - pSpaltenNr%3;
       //System.out.println("Start: ("+startZeile+"|"+startSpalte+")");
        for(int zeile = startZeile; zeile<startZeile+3; zeile++){
           for(int spalte = startSpalte; spalte<startSpalte+3; spalte++){
               int z= zahlen[zeile][spalte];
               if(z!=0){
                   if(verwendeteZahlen[z] == true){
                       return false;
                   }
                   verwendeteZahlen[z] = true;
               }
           }
       }
       return true;
   }
      
   /**
    * prueft, ob pZahl an der Position moeglich ist.
    * Veraendert zahlen aber nicht!
    * @param pZahl
    * @param pZeilenNr
    * @param pSpaltenNr
    * @return
    */
   public boolean istMoeglich(int pZahl, int pZeilenNr, int pSpaltenNr){
       // den Wert auslesen, um ihn hinterher wieder herstellen zu koennen.
       int z = zahlen[pZeilenNr][pSpaltenNr];
       zahlen[pZeilenNr][pSpaltenNr] = pZahl;
       if(!istOkZeile(pZeilenNr)){
           zahlen[pZeilenNr][pSpaltenNr] = z;
           return false;
       }
       if(!istOkSpalte(pSpaltenNr)){
           zahlen[pZeilenNr][pSpaltenNr] = z;
           return false;
       }
       if(!istOkQuadrat(pZeilenNr, pSpaltenNr)){
           zahlen[pZeilenNr][pSpaltenNr] = z;
           return false;
       }
       zahlen[pZeilenNr][pSpaltenNr] = z;       
       return true;
   }
   
   public int belegteFelder(){
       int ergebnis = 0;
       for(int zeile=0; zeile<9; zeile++){
           for(int spalte=0; spalte<9; spalte++){
               if(zahlen[zeile][spalte] != 0){
                   ergebnis++;
               }
           }
       }
       return ergebnis;
   }
   
   /**
    * berechnet, wie viele Moeglichkeiten es fuer dieses Feld gibt.
    * Wenn in dem Feld eine Zahl > 0 steht, dann wird sofort 0 zurueckgegeben.
    * @param pZeilenNr
    * @param pSpaltenNr
    * @return
    */
   public int wievieleMoeglichkeiten(int pZeilenNr, int pSpaltenNr){
       int ergebnis = 0;
       if(zahlen[pZeilenNr][pSpaltenNr] > 0){
           return 0;
       }
       for(int z=1; z<=9; z++){
           if(istMoeglich(z, pZeilenNr, pSpaltenNr)){
               //System.out.print(z);
               ergebnis++;
           }
       }
       //System.out.println();
       return ergebnis;
   }
   
   /**
    * bestimmt das Feld mit den wenigsten Moeglichkeiten.
    * Wenn es kein Feld mit Moeglichkeiten mehr gibt, wird {-1,-1} zurueckgegeben.
    * @return ein Array mit 2 Eintraegen: Index 0: zeile; Index 1: spalte
    */
   public int[] feldMitDenWenigstenMoeglichkeiten(){
       int[] minFeld = {-1,-1};
       int minMoeglichkeiten = 1000;
       for(int zeile=0; zeile<9; zeile++){
           for(int spalte=0; spalte<9; spalte++){
               int moeglichkeiten = wievieleMoeglichkeiten(zeile, spalte);
               // es werden nur Felder beruecksichtigt,
               // fuer die es mindestens eine Moeglichkeit gibt.
               if(moeglichkeiten > 0 && moeglichkeiten < minMoeglichkeiten){
                   minMoeglichkeiten = moeglichkeiten;
                   minFeld[0] = zeile;
                   minFeld[1] = spalte;
               }
           }
       }
       return minFeld;
   }
   
   /**
    *
    * @param zahl
    * @param zeile
    * @param spalte
    */
   public void eintragen(int zahl, int zeile, int spalte){
       zahlen[zeile][spalte] = zahl;
   }
}