MathePrisma Logo

Backtracking

Backtracking

Prinzip

Das Backtracking-Prinzip lässt sich elegant als rekursiver Algorithmus formulieren und dann auch so implementieren.

Definition

Ein rekursiver Algorithmus ist ein Algorithmus, der sich selbst wieder aufruft.

Backtracking
rekursiv

EF bezeichnet eine Entscheidungsfolge.

Algorithmus BacktrackingRek (EF)

falls EF Lösung ist
stop
sonst
für alle jetzt möglichen Entscheidungen
falls Entscheidung nicht erkennbar falsch
verlängere Entscheidungsfolge EF um diese Entscheidung,
(die verlängerte Entscheidungsfolge heiße EF')
BacktrackingRek(EF')

Der Algorithmus wird mit der leeren Entscheidungsfolge gestartet.

der Rechner spinnt den Ariadnefaden!

Bei Verwendung von Rekursion muss man sich keine Gedanken mehr darüber machen, wie man eine Entscheidung zurücknimmt: der Rechner organisiert dies von sich aus beim Verwalten der rekursiven Aufrufe.

mehr zum Stack im Modul Lineare Datenstrukturen

Der Rechner verwaltet eine Datenstruktur Stack ('Stapel').

  • Bei jedem rekursiven Aufruf werden die aktuellen Parameter auf den Stapel gelegt ('gemerkt').
  • Nach Rückkehr ('return') von einem rekursiven Aufruf werden die dann aktuellen Parameter wieder vom Stack eingelesen.

Beobachte, wie die rekursive Version des Algorithmus Zum Ausgang für ein kleines Labyrinth abläuft.
Die Parameter EF, M und X werden jeweils im Stack verwaltet.