Das Backtracking-Verfahren

Letztmalig dran rumgefummelt: 20.12.07 11:32:56

	Das Backtracking-Verfahren ist mit Sicherheit eines der Basisverfahren zur Lösung komplexer Probleme. Dem Leben abgeschaut versucht es, einen Weg genau so lange zu verfolgen, bis eindeutig nachgewiesen ist, dass es auf diesem Wege keine im Zusammenhang mit der Aufgabe stehende Lösung geben kann. Jeder Wanderer, der einmal die Orientierung verloren hat, kennt dieses Problem und hat es schon mindestens einmal erfolgreich gelöst, da er ansonsten diese Zeilen ja gar nicht zur Kenntnis nehmen könnte ;-)
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Lösbarkeit und Problemlösungsstrategien Logo für das Backtracking-Verfahren Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???
	Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer sowie deren Optimierung durch Computer

1. Problembeschreibung

	Zur Anzahl der jeweils vorhandenen Kanninchenpaare kommen im Folgemonat deren Jungtiere hinzu, welche zwei Monate später wieder Nachwuchs haben (zumindest nach dem theoretischen Idealmodell).
	Rekursive Baumstruktur des Aufrufes der Fibonacci-Funktion

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	Der Lösungsalgorithmus für die Fibonacci-Funktion
	effiziente Lösung nur als rekursiver Algorithmus
	Die lineare Folge von Aufrufen wird durch dieses Beispiel eindeutig erkennbar, und die Eingabewerte n hatten nur eine Anzahl von n + 1 Aufrufen zur Folge. Es lässt sich rein rechnerisch leichter nachvollziehen. Bei den Messungen zur Laufzeit konnte keine Verzögerung festgestellt werden. Die Vorteile der endrekursiven Lösung sind sehr gut nachweisbar. Kein Stacküberlauf konnte bei einem Eingabewert von 40 festgestellt werden.

3. Lösungsalgorithmus

Wenn es mindestens einen Lösungsansatz gibt, dann versuche, aus den gegebenen Wortpaaren identische Sätze auf beiden Seiten der Gleichung zu bilden. Wiederhole dies solange, bis keine weitere Möglichkeit mehr existiert.

Beispiel: Gesucht ist die 6. Zahl in der Fibonacci-Folge: Fibonacci(0) = 1 Fibonacci(1) = 1 Fibonacci(2) = Fibonacci(2-1) + Fibonacci(2-2) + Fibonacci(1) = 2 Fibonacci(3) = Fibonacci(3-1) + Fibonacci(3-2) + Fibonacci(2) = 3 Die Fibonacci’schen Zahlen beschreiben das Anwachsen einer Kaninchenfamilie von Generation zu Generation, und zwar unter der Annahme, dass: alle Tiere unbegrenzt am Leben und zeugungsfähig bleiben und dass: jedes Tier in regelmäßigen Zeitabständen mit Ausnahme des ersten Intervalls nach seiner Geburt ein neues Tier zur Welt bringt - und zwar immer vom gleichen Geschlecht wie das jeweilige Elterntier

4. Programmvorschläge

	Rufprozedur in LOGO pr fibo :n    (wenn :n = 0 [rg 0]~                 [(wenn :n = 1 [rg 1]~                               [rg sum fibo :n-2 fibo :n-1])]) ende
	Fibonacci-Zahlen als Excel-Tabelle (das geht gut und ohne Rekursion)

5. Zusammenfassung

	Hier greifen wir unter anderem die Argumente für einen Algorithmus auf und vergleichen, ob Übereinstimmung in allen Punkten gegeben ist.
	Endlichkeit der Beschreibung ist gegeben
	Eindeutigkeit ist gegeben - jeder Schritt ist für jede Bedingung eindeutig fest vorgegeben und lässt keine Abweichung zu
	Effektivität ist gegeben - jeder Schritt ist ausführbar
	Terminierung ist nicht gegeben - der Algorithmus läuft nach erreichen des Zwischenergebnisses 91 ewig und generiert einen Stapelüberlauf
	Determiniertheit ist gegeben, der Folgeschritt nach einer Operation ist immer bekannt

6. Weiterführende Literatur

	Walter Kranzer; „So interessant ist Mathematik“; VEB Deutscher Verlag der Wissenschaften Berlin 1989; © 1989 by Aulis Verlag Deubner & Co. KG Köln

7. Links zum Thema

	http://www.panix.com/~derwisch/hannes/elug/lisp/scheme.pdf
	http://www-is.informatik.uni-oldenburg.de/~dibo/teaching/java9900/vorlesungen/vorlesung7/tsld031.htm
	http://www.lexikon-definition.de/LISP.html

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rucksackproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im Dezember 2007