Was ist eigentlich … Backtracking?  

von | Aug. 29, 2022 | Python | 0 Kommentare

Was ist eigentlich … Backtracking?

Backtracking oder Rückwärtsverfolgung beschreibt einen Algorithmus, bei dem die Lösung einer Aufgabe durch systematisches Probieren gesucht wird. Dabei werden die Lösungsschritte für jede Teillösung nach folgendem Schema ermittelt:

  1. Zuerst wird festgestellt, welche Werte in für die konkrete Teillösung möglich sind.
  2. Dann wird überprüft, ob der erste Wert zu einer gültigen Lösung führen kann.
  3. Wenn ja, wird Vorgang für die nächste Teillösung (Schritt (1)) fortgesetzt.
  4. Wenn nein, wird der nächste Wert für die Teillösung untersucht.
  5. Wenn keine Werte mehr übrig sind, ist bei der vorhergehenden Teillösung der nächste Wert zu nehmen.

Der Vorgang wird gern anhand des Königinnenproblems (auch Damenproblem genannt) auf einem Schachbrett erklärt. Eine Königin kann eine andere Figur in desselben Zeile, derselben Spalte und derselben Diagonale schlagen. Die Aufgabe lautet, acht Königinnen so auf dem Schachbrett aufzustellen, dass keine eine andere schlagen kann.

In der Wikipedia ist der Vorgang im Detail beschrieben: https://de.wikipedia.org/wiki/Damenproblem

4 Königinnen

Probieren wir das Ganze mit vier Königinnen auf einem 4×4-Schachbrett: das ist leichter überschaubar. Da wir später ein Programm dazu schreiben werden, verwenden wir die in der Informatik übliche Zählweise beginnend mit 0.

Wenn wir die Felder mit der Zeilennummer (row, r) und der Spaltennummer (Column, c) bezeichnen, sind das die Feldnummern (r, c):

  • Bild 1: Wir beginnen links oben, Platz (0,0)
  • Bild 2: In der Zeile 0 kann keine weitere Königin stehen. Daher weiter in der Zeile 1. Der erste mögliche Platz ist in Spalte 2
  • Bild 3: Aber schon gibt es keinen Platz mehr in der Zeile 1. Daher muss die Königin in Zeile 2 in Spalte 3 rücken
  • Bild 4: Der Platz in Zeile 2 und Spalte 1 passt
  • Bild 5: Aber nun ist kein Platz in Zeile 3. Die Königin in Zeile 2 hat in dieser Zeile keinen Platz mehr. Auch die Königin in Zeile 1 kann nicht mehr weiterbewegt werden. Daher zurück in Zeile 0 – neue Position in der Spalte 1
  • Bild 6: Weiter in Zeile 1
  • Bild 7: Weiter in Zeile 2
  • Bild 8: Und mit Zeile 3 ist die Lösung fertig

Es gibt noch eine zweite Lösung, die symmetrisch zur ersten ist – Bild 9:

Unter https://www.mathematik.ch/spiele/N_Damenproblem/ wird der Ablauf animiert dargestellt. Größe und die Verzögerung zwischen den einzelnen Schritten können eingestellt werden.

Lösung per Programm

Alle Programme dieses Beitrags können direkt vom Webserver geladen, in ein Verzeichnis kopiert und auch gleich mit Python 3 gestartet werden. Auf weitere Programmdateien wird im Text verwiesen. Sie sind hier nicht abgedruckt sind, aber die Dateien sind dort ebenfalls zu finden. Die Namen der Programmdateien sind hier hervorgehoben.

Der Algorithmus wiederholt im Schritt (c) den Vorgang ab Schritt (a). Programmtechnisch wird das zu einer Rekursion – das ist eine Funktion, die sich selbst aufruft.

Im Internet sind viele Programmbeispiele in unterschiedlichen Sprachen zu finden. Aber wir wollen einen Schritt weiter gehen. Die Idee „Backtracking“ lässt sich auf viele Probleme anwenden, auch auf typische Rätsel, wie sie beispielsweise in der Presse an jedem Sonntag veröffentlicht werden:

https://www.diepresse.com/5789519/die-erweiterte-raetselseite-der-presse-am-sonntag-zum-ausdrucken

Die objektorientierte Programmierung erlaubt die Trennung zwischen dem grundlegenden Algorithmus „Backtracking“ und der konkreten Aufgabenstellung, also einem konkreten Rätsel als abgeleitete Klasse. In einem Artikel in der Zeitschrift der ACM wurde dieser Lösungsweg (erstmalig?) vorgestellt: „An Object-Oriented View of Backtracking“ (Robert E. Noonan et.al., https://dl.acm.org/doi/pdf/10.1145/331795.331886). Der folgende Lösungsvorschlag orientiert sich daran und ist in Python 3 geschrieben.

Backtrack objektorientiert

Zuerst einmal die Klasse Backtrack0, Programmdatei: backtrack0.py, in der der grundlegende Backtrack-Algorithmus implementiert wird:

Backtrack0

# File backtrack0.py

# Inspiriert von

# https://dl.acm.org/doi/pdf/10.1145/331795.331886

 

class Backtrack0(object):

 

    def __init__(self):        

        self.attempt(0)  

   

    def moves(self, level:int):

        raise NotImplementedError()

 

    def valid(self, level:int, move):

        raise NotImplementedError()

 

    def record(self, level:int, move):

        raise NotImplementedError()

 

    def undo(self, level:int, move):

        raise NotImplementedError()

 

    def done(self, level:int):

        raise NotImplementedError()

 

    def attempt(self, level: int) -> bool:

        successful: bool = False

        for move in self.moves(level):          

            if self.valid(level, move):

                self.record(level, move)

                if self.done(level):

                    successful = True

                    self.undo(level, move)                    

                else:

                    successful = self.attempt(level+1)

                    if not successful:

                        self.undo(level, move)

 

Erklärungen zum Programm

Eine Reihe von Methoden sind Platzhalter, die erst bei einer konkreten Aufgabe im Detail in die abgeleitete Klasse eingefügt werden. Ein Aufruf hier führt zu einer Fehlermeldung.

  • moves liefert für die Methode attempt jene Werte, die der Reihe nach auszuprobieren sind. Gegebenfallss werden Werte, die zu keiner Lösung führen können, gar nicht in die Liste aufgenommen.
  • valid überprüft, ob der Wert move im Schritt level ein gültiger Wert ist.
  • record speichert den von valid überprüften Wert ab.
  • undo entfernt den Wert wieder, wenn mit ihm keine Lösung möglich ist.
  • done prüft, ob alle Schritte schon erledigt sind und das Rätsel gelöst ist. In diesem Fall wird die Lösung auch gleich ausgegeben und nach einer weiteren Lösung gesucht.
  • attempt ist die zentrale Methode, die die vorher genannten Methoden verwendet. Sie wird mit dem Startwert 0 beim Initialisieren durch __init__ aufgerufen.

Warum englische Bezeichnungen für die Methoden? Einerseits um den Vergleich mit dem ACM-Artikel zu ermöglichen, andererseits um eine Veröffentlichung dieses Beitrags in anderen Medien zu erleichtern.

Viele Versuche waren für die Lösung vorwendig? Wie lange hat die Suche gedauert? Dazu erweitern wir Backtrack0 zu Backtrack. Auf Backtrack bauen dann auch alle folgenden Beispiele auf.

Backtrack

# File backtrack.py

import time, sys

from backtrack0 import Backtrack0

 

class Backtrack(Backtrack0):

 

    attempts = 0

    showAttempts = False

 

    def __init__(self, test:bool = False, showAttempts:bool = False):

        self.test = test

        start = time.time()

        self.attempt(0)

        end = time.time()

        self.showAttempts = showAttempts

        if showAttempts:

            print(f„\n{self.attempts:16_d} attempts“

              f“ in {end-start:8,.2f} seconds“)

   

    def attempt(self, level: int) -> bool:        

        if self.attempts>100_000:

            if self.attempts % 5_000_000 == 0:

                print(f„\n{self.attempts//1_000_000:4_d} Millionen „, end=„\n“)

           

            if self.attempts % 100_000 == 0:

                print(„.“, sep=„“, end=„“)

       

        successful: bool = False

        for move in self.moves(level):

            self.attempts += 1

            if self.test:

                print(f„attempt-test: level:{level}  move:{move}„)

            if self.valid(level, move):

                self.record(level, move)

                if self.done(level):

                    successful = True

                    self.undo(level, move)

                   

                else:

                    successful = self.attempt(level+1)

                    if not successful:

                        self.undo(level, move)

 

Weitere Hinweise

  • Bei langen Rechnungen sollte angezeigt werden, ob das Programm noch „lebt“. Daher wird nach je 100.000 Versuchen ein Punkt ausgegeben und nach jeweils 5.000.000 Versuchen ein Text.
  • Mit print(..., end="") werden die einzelnen Punkte nebeneinander und nicht untereinandergeschrieben.
  • Zahlen können mit einem „_“-Zeichen leichter lesbar gemacht werden. Die Erfinder der IBAN hatten leider keine vergleichbare Idee.
  • Das Programm verwendet Formatstrings:  formatted string literals, siehe https://docs.python.org/3/tutorial/inputoutput.html und https://docs.python.org/3/library/string.html#formatspec.  Wer sie noch nicht kennt: bitte unbedingt eine der vielen Dokumentationen dazu im Internet lesen!
  • In __init__ wird der Formatstring in der nächsten Zeile fortgesetzt. Der Fortsetzungsstring muss auch mit f beginnen.

Kommentar absenden

Zur Werkzeugleiste springen