0. Inhaltsverzeichnis 

1. Standardalgorithmen 

 
2. Das Divide-and-Conquer-Prinzip 
2.1 Das Heron-Verfahren und seine Umsetzung als Rekursionsalgorithmus 
2.2 Die Türme von Hanoi 
 
3. Das Backtracking-Prinzip 
3.1 Allgemeines 
3.1.1 Die Idee 
3.1.2 Vorleistungen 
3.1.3 Zielstellungen 
3.1.4 Beispiele für Backtracking-Verfahren 
3.1.5 Darstellungsformen 
3.1.6 Tangierte Themen 
3.1.7 Literatur
3.2 Das Königsberger Brückenproblem 
3.3 Das Labyrinth 
 

3. Das Backtracking Verfahren

3.1 Allgemeines

3.1.1 Die Idee

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. 
 

3.1.2 Vorleistungen

3.1.3 Zielstellungen

     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. 
 

3.1.4 Beispiele für Backtracking-Verfahren

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.] 
 

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. 
 

3.1.6 Tangierte Themen

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. 
 

3.1.7 Literatur