backtracking und Induktionsprinzip

[eleve]

Hey,

also ich hab ne Frage zu dem Induktionsprinzip beim backtracking.

Es gibt ja überall das Beispiel mit dem Gnom und dem labyrinth.

Soweit hab ich das Backtracking auf verstanden:

Es wird die bereits "gegangene" Strecke gemerkt und es wird wenn man in einer Sackgasse ist wieder an den Punkt bevor man "abgebogen" ist zurückgesetzt.

Und so im Prinzip weiß ich auch was das Induktionsprinzip ist:

Also ich habs so verstanden, dass man ein Problem aufspaltet auf einen oder mehrere Basisfälle und immer wenn so ein Basisfall abgearbeitet ist, wird das Problem quasi um 1 verringert.



Aber mir ist jetzt unklar, was jetzt beim Backtracking mit dem Gnom und dem Labyrinth einen solchen Basisfall darstellt?

Ich versteh es nicht ganz.. denn wann ist so ein basisfall rum? und woher weiß man wohin man zurücksetzen muss?

 

[SlaterB]

ich kannte den Gnom noch nicht, aber schnell gefunden:
Backtracking erklärt - Moritz Lenz

als Basisfall kann man hier bezeichnen was eben der Gnom die ganze Zeit macht: er kommt immer nur zu einer Kreuzung und geht dort links, oder in eine andere Richtung oder zurück,
dieser Einzelschritt ist in der wiederholten Anwendung in der Gesamtsicht die komplette Lösung

> woher weiß man wohin man zurücksetzen muss?
woher es der Gnom weiß steht doch da, einfach die Info merken,
ok, er weiß nur wo er schon war, nicht unbedingt welcher Weg jeweils 'zurück' bedeutet, da muss man schon differenziert merken, der Gnom vielleicht am Alter der Duftstoffe..,

wenn man programmiert mit Rekusion ist es noch leichter, dann hat man offene Methodenaufrufe jeweils mit lokalen Variablen,
kann sich auf ganz natürliche Weise Informationen merken, zurück ist besonders einfach, das ist das Ende der aktuellen Methode

in Schleifen programmiert muss man alles irgendwo ablegen,
Liste der besuchten Kreuzungen, jeweils Anzahl ausprobierter Wege von dort aus und was immer nötig ist, etwa auch der Rückweg

 

[muckelzwerg]

Backtracking ist ein rekursives Verfahren. Und solche Rekursionen in der Programmierung sind im Prinzip die Umkehrung eines Induktionsbeweises.
Oder andersrum formuliert ist der Rekursionsbeweis das Abklappern einer rekursiven Definition.

Nimm mal die Fakultät als Beispiel.

public static int fakultaet(int a){
                if(a==0){
                        return 1;
                }else{
                        return a*fakultaet(a-1);
                }
        }

Jeder Wert Fak(x) ist rekursiv definiert über seinen Vorgängerwert Fak(x-1) und wird mit der Formel x * Fak(x-1) gebildet.
Irgendwo muss das aber mal "enden". Deshalb gibt es die Definition "Fak(0) := 1".
Jetzt dreh das Ganze mal um, dann bekommst Du die Induktion.
Als Induktionsanfang hast Du die Definition. und die Formel. Dementsprechend gilt dann
"Wenn Fak(a) = y dann Fak(a+1) = (a+1)*Fak(a). Da gibt es nicht mehr viel zu "beweisen", weil es ja eben genau so rekursiv definiert wurde. (für gewöhnlich will man ja eher die Formel beweisen anstatt, dass man sie selbst festlegen kann.)
Und diese Kette von Induktionsschritten löst Du rückwärts auf, wenn Du eine rekursive Funktion schreibst.

Beim Backtracking kommt jetzt noch dazu, dass Du die Rekursion bis zum Ende auflöst und dann feststellst "nö, hier gibts die gesuchte Definition nicht". Meist wird damit ja etwas gesucht, z.B. der Ausgang des Labyrinths. Wenn Deine Rekursion "endet" (weil kein Schritt mehr übrig ist) dann schaust Du auf die aktuelle Position und stellst fest
"Dumm gelaufen, das ist leider nur die Rekursive Definition einer Sackgasse". Damit hast Du im Prinzip einen induktiven Beweis geliefert, dass von dieser Sackgasse ein Weg zu Deinem Startpunkt führt.
Damit bist Du aber nicht zufrieden. Also gehst Du auf dem Weg, den Du gekommen bist, zurück bis Du eine Abzweigung findest.
Hier musstest Du auf dem Hinweg eine Entscheidung treffen. Die hat Dich in die Sackgasse geführt, also entscheides Du diesmal anders.
Damit Du alle Abzweigungen durchprobieren kannst, markierst Du die irgendwie. Im Programm passiert das "automatisch", weil der Ablauf in die nächste Zeile springt und die alte Abzweigung nicht mehr erreichen kann. Würdest Du zu Fuß rumlaufen, müsstest Du Nummern an die Abzweigungen schreiben oder sowas.
Auf diese Weise machst Du eine "Tiefensuche" durch den ganzen Raum und findest den Weg nach draußen, wenn es einen gibt.