Suche Home Einstellungen Anmelden Hilfe  

Standardalgorithmen
 
  
Anfang
vor
  

3. Das Backtracking Verfahren

3.1 Allgemeines

3.1.1 Die Idee

Ein Backtracking - Algorithmus gehört zur Gruppe der trial-and-error-Verfahren (versuchen und nachprüfen). Es wird 
versucht, eine Teillösung systematisch zu einer Gesamtlösung auszubauen. Es werden alle möglichen Lösungswege untersucht. 
Falls zwischendurch ein weiterer Ausbau einer Teillösung nicht mehr möglich ist (Sackgasse), werden Teilschritte rückgängig 
gemacht. Die reduzierte Teillösung wird versucht, auf anderem Wege wieder auszubauen. Diese Wiederholung erfolgt, bis eine 
Lösung gefunden wurde, oder erkannt wird, daß keine Lösung existiert. Typisch für Backtracking ist das Laufen in Sackgassen 
und wieder herausfinden. 

Zurückgeführt wird das Verfahren auf Walker (1958). Es sollte dann angewandt werden, wenn kein besseres Verfahren zur 
Lösung bekannt ist, als alle Kandidaten systematisch zu prüfen. 
 

  
Anfang
vor
zurück
  

3.1.2 Vorleistungen

Die unterrichtliche Behandlung der Rekursion ist eine Voraussetzung zur Erschließung der Lösungsidee. Für die meisten hier 
genannten Beispiele sollte die Datenstruktur ARRAY bekannt sein. Für das Springerproblem, das n-Damen-Problem, das 
Labyrinthproblem, das Problem der stabilen Heirat drängt sich diese Datenstruktur geradezu auf, nach Modellierungen erweist 
sie sich auch bei den anderen Beispielen als geeignet. 
 
 
  
Anfang
vor
zurück
  

3.1.3 Zielstellungen

Backtracking - Verfahren bieten mehrere Ansätze für die Zielorientierung im Unterricht. Je nach Aufgabenstellung lassen sich 
problemlos folgende Varianten realisieren: 

     Finden einer Lösung 
     Finden aller Lösungen 
     Finden der optimalen Lösung 
     Variantenvergleiche 

Außerdem werden Zielvariationen möglich sein, wenn z.B. eine Lösung gefunden wurde, kann durch Präzisierung der 
Aufgabenstellung das Finden aller Lösungen thematisiert werden. 
 

  
Anfang
vor
zurück
  

3.1.4 Beispiele für Backtracking-Verfahren

Genannt werden hier einige, aufgrund ihrer Anschaulichkeit für den Unterricht gut geeignete Beispiele für Backtracking. Durch 
die Literaturangabe wird auf eine genauere Formulierung verwiesen. 

Das Königsberger Brückenproblem 
In der Innenstadt von Königsberg vereinen sich der Alte und der Neue Pregel zum Pregelfluß. Im 18. Jh. führten über die 
Flußläufe sieben Brücken. Gesucht ist ein Weg, der über jede Brücke genau einmal führt. [Duden Informatik, 
Engesser/Claus/Schwill, Dudenverlag, Mannheim, 1993, S. 347] 

Das Labyrinthproblem 
Man befindet sich in einem Labyrinth und versucht, einen Weg heraus zu finden. [Duden Informatik, Engesser/Claus/Schwill, 
Dudenverlag, Mannheim, 1993, S. 51] 

Das N - Damen Problem 
Es sind n Damen auf einem n x n - Schachbrett so aufzustellen daß keine Dame eine andere bedroht. [Algorithmen und 
Datenstrukturen, N. Wirth, Teubner Verlag, Stuttgart, 1983, S. 168 ff.] 

Das Problem der stabilen Heirat 
Aus einer Menge von Männern und einer Menge von Frauen werden Paare gebildet. Jede Frau und jeder Mann hat eine 
Wunschliste der Partner in der Reihenfolge ihrer Bevorzugung aufgestellt. Wenn die Ehepaare so gewählt werden, daß es einen 
Mann und eine Frau gibt, die nicht miteinander verheiratet sind, die sich gegenseitig aber vor ihren tatsächlichen Ehepartnern 
den Vorzug geben würden, dann ist die Wahl instabil. Existiert kein solches Paar so ist die Wahl stabil. [Algorithmen und 
Datenstrukturen, N. Wirth, Teubner Verlag, Stuttgart, 1983, S. 174 ff.] 

Das Rucksackproblem 
Ein Rucksack mit einer maximalen Tragfähigkeit soll mit Gegenständen unterschiedlicher Masse und unterschiedlicher Werte 
gepackt werden. Die Tragfähigkeit des Rucksacks darf nicht überschritten werden, andererseits soll der Wert der Gegenstände 
möglichst groß werden. [Duden Informatik, Engesser/Claus/Schwill, Dudenverlag, Mannheim, 1993 S. 606 f.] 

Das Springerproblem 
Ausgehend von einem Anfangsfeld sucht ein Springer auf einem Schachbrett nach den Schachregeln einen Weg, der ihn genau 
einmal über jedes Feld führt. [Algorithmen und Datenstrukturen, N. Wirth, Teubner Verlag, Stuttgart, 1983, S. 163 ff.] 

Nachbarschaftsprobleme 
Wimpel verschiedener Farbe und unterschiedlicher Anzahl sollen so aufgehängt werden, daß keine zwei benachbarten Wimpel 
die gleiche Farbe haben [15. Bundeswettbewerb Informatik, Aufgabe 1] 

Wegeprobleme 
Ein Handlungsreisender soll bestimmte Orte bereisen. [Grund- und Leistungskurs Informatik, Rollke, Sennholz, Cornelsen, 
Berlin, 1994, S. 109 ff.] 
 

  
Anfang
vor
zurück
  

3.1.5 Darstellungsformen

 
 

Das Problem kann bei diesen Beispiele in den meisten Fällen mit einer Skizze veranschaulicht werden. Unwesentliche 
Bestandteile werden im einsetzenden Prozeß der Modellierung vernachlässigt und es entstehen nicht selten Lösungsbäume und 
Graphen. Durch fortschreitende Modellbildung läßt sich häufig eine Adjazenzmatrix entwerfen, geeignete Datenstrukturen bieten 
sich an. Struktogramme bereiten das Schreiben von Programmen vor. Die Abstraktionsformen und der Abstraktionsgrad 
können variieren. Verschiedene Phasen der Modellierung eines Problems sind darstellbar. 
 

  
Anfang
vor
zurück
  

3.1.6 Tangierte Themen

Das Backtracking - Verfahren bietet die Möglichkeit, eine Vielzahl von Ideen, Algorithmen und Datenstrukturen am komplexen 
Beispiel zu behandeln. Darum bietet sich das Verfahren besonders in der Systematisierungsphase an. So können verschiedene 
Bereiche noch einmal aus anderer Sicht betrachtet werden. Ausgehend von einer Strukturierung des Problems bietet sich stets 
die Möglichkeit zur Abstraktion, um andere Beispiele in zunehmender Selbständigkeit des Schülers zu lösen. 

Verschiedene Datenstrukturen sind denkbar. Wenn auch in den meisten Fällen das ARRAY am Meisten geeignet erscheint, 
sind auch andere Datenstrukturen möglich. Iterations- und Rekursionslösungen können als verschiedene Varianten 
gegenübergestellt werden. 

Wenn nach dem Finden einer Lösung alle Lösungen gefunden werden sollen, steht die Terminierung im Mittelpunkt. Fragen zur 
Laufzeiteffizienz lassen sich aufwerfen, ebenso wie Optimierungsüberlegungen. Die vielen Gestaltungsvarianten versprechen 
einen interessanten Unterricht. Eine Lösung für eine Gruppe von Problemen zu finden stellt einen intellektuell hohen Anspruch 
dar. 
 

  
Anfang
zurück
  

3.1.7 Literatur

[Algorithmen in C, R. Sedgewick, Addison-Wesley, 1993] 
[Algorithmen und Datenstrukturen, Ottmann/Widmayer, Spektrum Verlag, 1996] 
[Algorithmen und Datenstrukturen, N. Wirth, Teubner Verlag, Stuttgart, 1983] 
[Duden Informatik, Engesser/Claus/Schwill, Dudenverlag, Mannheim, 1993] 
[Einheitliche Prüfungsanforderungen in der Abiturprüfung Informatik, Luchterhand, 1991] 
[Grund- und Leistungskurs Informatik, Rollke, Sennholz, Cornelsen, Berlin, 1994] 
[Prinzipien des Agorithmenentwurfs, T. Ottmann, Spektrum Verlag, 1998] 
 
  
Anfang
  
 

Benutzer: Gast • Besitzer: seminar • Zuletzt geändert am: