Rekursion - Programmieren Spielend Gelernt mit dem Java-Hamster-Modell - page 329

0 übergeben. In der dritten Inkarnation der Prozedur ist die Bedingung der if-Anweisung nicht mehr
erfüllt, sodass es zu keiner weiteren Erzeugung einer Inkarnation kommt.
17.7 Backtracking
Unter Backtracking versteht man ein Lösungsverfahren, bei dem versucht wird, eine Gesamtlösung
eines gegebenen Problems dadurch zu entwickeln, dass eine Teillösung systematisch zur Gesamt-
lösung ausgebaut wird. Falls in einem bestimmten Stadium ein weiterer Ausbau einer vorliegenden
Teillösung nicht mehr möglich ist (man ist in eine „Sackgasse“ gelaufen), werden einer oder auch
mehrere der letzten Teilschritte rückgängig gemacht. Die dann reduzierte Teillösung versucht man
anschließend auf einem anderen Weg wieder auszubauen. Dieses Zurücknehmen von Teilschritten
und erneute Probieren anderer Teilschritte wird solange wiederholt, bis eine Lösung des gegebenen
Problems gefunden ist oder bis erkannt wird, dass keine Lösung existiert.
Das Prinzip der Rekursion eignet sich hervorragend zum Lösen von Backtracking-Problemen. Die
Teilschritte werden dazu in Form einer rekursiven Funktion formuliert.
Schauen Sie sich das folgende Problem an: Der Hamster steht, wie in Abbildung 17.2 beispielhaft
skizziert, am Eingang eines Zyklen freien Labyrinths. Er soll das Labyrinth nach Körnern durchsu-
chen. Sobald er ein Korn findet, soll er dies aufnehmen und auf dem schnellsten Weg wieder zum
Eingang zurückkehren.
Abbildung 17.2: Labrinthdurchsuchung via Backtracking-Verfahren
Das folgende Hamster-Programm bedient sich des Backtracking-Verfahrens zur Lösung des Pro-
blems:
boolean gefunden = false;
void main() {
sucheGangAb();
}
void sucheGangAb() {
if (kornDa()) { // Problem geloest