Animation: Backtracking

Animation Systems Collection -- Animations Collection

Description

Die Strategie Backtracking besteht darin, ein zu lösendes Problem in Teilprobleme zu zerlegen, so daß eine Entscheidungsbaum entsteht. (Aus Platz- und Zeitgründen wird dieser Baum in der Regel nicht tatsächlich aufgebaut, sondern dient mehr als Orientierungshilfe).

Die Teilzweige werden dann systematisch der Reihe nach erfolgt und bei Erkennung einer "Sackgasse" als nicht möglich markiert. Sobald die erste Lösung gefunden wurde, bricht das Verfahren ab.

In ungünstigen Fällen ist die komplette Berechnung aller Teilzweige notwendig, was in der Regel zu exponentiellem Aufwand führt.

Die Animation verwendet als Beispiel das 4-Damen Problem Problem, bei dem vier Damen so auf einem 4x4-Brett anzuordnen sind, daß keine Dame eine andere schlagen kann. Das 4-Damen-Problem ist eine verkleinerte Fassung des 8-Damen-Problems. Man kann sich leicht überlegen, daß es für 2 oder 3 Damen auf einem 2x2 bzw. 3x3 Feld keine Lösung geben kann.

Unter dem Brett mit den Damen wird der Algorithmus verbal beschrieben; in den einzelnen Schritten wird die ausgeführte Aktion farblich hervorgehoben.

Screen Shot(s):

Grundsätzliches Vorgehen

4-Damen-Problem - Zugmöglichkeiten einer Dame

Sackgasse auf dem Lösungsweg

Fortsetzung mit nächster Möglichkeit

Classification

• Algorithms
• Algorithmic Strategies

Animation Rating

You can provide a rating for this animation. The rating is performed on a scale of 1 to 10, where 10 is the highest possible grade.

1(very bad) 2 3 4 5 6 7 8 9 10(very good)

File information

Title	Backtracking
Animation URL	http://www.animal.ahrgr.de/Anims/de/backtracking.aml
Animation Applet	Animal Applet
Animation System	Animal
Animation Type	dynamic full VCR
Supported OS(s)	Linux,MacOS,Windows 95,Windows 98,Windows ME,Windows NT,Windows 2000,Unix
Author(s)	Guido Rößling
Date	1999-05-03
File Size size	5245 Byte
Number of Accesses:	6369
Added to DB by	Guido Rößling
Average Rating	5.3333(21 submitted ratings)
Language:	de
Number of Accesses:	6369

BibTeX bibliographic entry for citations:

@Misc{Rößling:1999,
   author = {Guido Rößling},
   title = {Backtracking},
   howpublished = {WWW: \url{http://www.animal.ahrgr.de/Anims/de/backtracking.aml}},
 }