Inhaltsverzeichnis 1 Einführung 2 Heuristiken 3 Begriff 3.1 Anwendungsgebiete 3.1.1 Wirtschaftswissenschaften 3.1.2 Philosophie 3.1.3 Psychologie 3.1.4 Mathematik 3.1.5 Informatik 3.2 Springerproblem 3.2.1 Erläuterung des Springerproblems 3.2.2 Lösung mit Backtracking 3.2.3 Warnsdorff Heuristik 4 Lokale Suche 4.1 Verzweigen und Begrenzen 4.2 Greedy-Heuristiken 4.3 Hill climbing 4.4 Threshold accepting 4.5 Simulated annealing 4.6 Tabu-Suche 4.7 Sintflut-Algorithmus 5 Fazit 6 Übungsaufgaben 7 Quellen 7.1 Literatur 7.2 Weblinks

Autoren:

1. Patrick Breite (sipabrei@stud.hs-zigr.de)
2. Marcel Mücke (simamuec@stud.hs-zigr.de)

Einführung

Das Thema der Effizienten Näherungsalgorithmen baut zum teil auf andere Themenkomplexe auf,die sehr zu empfehlen sind:
1. Probabilistische Algorithmen
2. P-NP-Problem

Heuristiken

Begriff

Der Begriff Heuristik ist aus dem altgriechischen Wort "heuriskien" abgeleitet und bedeutet so viel wie "(auf)-finden" bzw. "entdecken".

Anwendungsgebiete

Wirtschaftswissenschaften

Philosophie

Psychologie

Mathematik

Informatik

Springerproblem

Erläuterung des Springerproblems

Vor mehr als 200 Jahren formulierte der Schweizer Mathematiker Leonhard Euler erstmals das Problem des Rösselsprungs, auch Springerproblem genannt:

"Gibts es für einen Springer einen Weg, der jedes Feld eines n x n-Schachbrettes genau einmal besucht?"

Um diese Problem lösen zu können, muss bekannt sein, dass ein Springer eine Schachfigur ist, welche von ihrem aktuellem Feld A(x_1 , y_1) zu einem Feld B(x_2 , y_2) bewegt werden kann, wobei zu beachten ist das entweder

|x_1 - x_2| = 1 und |y_1 - y_2| = 2

oder

|x_1 - x_2| = 2 und |y_1 - y_2| = 1

für die Bewegungen des Springers gelten muss.

Auf dem folgenden Bild sind die möglichen Züge eines Springers zu erkennen.

Lösung mit Backtracking

Lange Zeit war für die Lösung des sogenannten Rösselsprungs nur der Naive Algorithmus mit Backtracking bekannt, wodurch ein Exponentieller Aufwand Zeitaufwand entsteht. Der Versuch mit diesem Algorithmus eine Lösung für ein n x n-Schachbrett mit n>7 zu finden ist nur mit enormem Zeitaufwand zu lösen, da bei einem 8 x 8-Schachbrett bereits über 3 Milliarden Züge überprüft werden müssten um mit einem reinen Backtracking Algorithmus zum Ziel zu gelangen.

Ein Applet welches mit einem eingeschränkten Backtracking algorithmus arbeitet finden sie hier. Es ist zu beachten dass in diesem Algorithmus bestimmte Sackgassen schon vor dem Programmstart ausgeschlossen werden, um die Lösung diese 8 x 8-Schachbretts in einer möglichst kurzen Zeit zu gewährleisten.

Warnsdorff Heuristik

Die Warnsdorff Heuristik wurde 1823 von H.C. Wanrsdorff entwickelt und der Grundgedanke ist, dass ein Feld mit wenigen Folgefeldern schnell isoliert werden und so nicht mehr besucht werden können.

Warnsdorff entwickelte desshalb folgende Regeln:

1. Ziehe auf das Feld mit der geringsten Zahl an noch zu erreichenden unbesuchten Folgefelder.

2. Wenn 2 oder mehr Felder die selbe Anzahl an noch zu erreichenden unbesuchten Folgefelder aufweisen ziehe auf das Feld, welches zuletzt (oder zuerst) betrachtet wurde.

Wenn man Beispielsweise die 1. Regel auf ein anwendet auf ein noch leeres Schachbrett sieht dies folgendermaßen aus:

<eval id="4c0e16e3c7564"> </eval> Die Heuristik von Warnsdorff garantiert jedoch nur eine näherungsweise Lösung des Springerproblems, da bei größeren Schachbrettern nicht alle Sackgassen gemieden werden, was für Warnsdorff unmöglich zu untersuchen war, da er noch keine Computer zur Verfügung gehabt hat, welche diese Springertour auf beispielsweise einem 100x100 großem Schachbrett errechnen.

Weiterhin kann man zeigen, dass es für Schachbretter der Größe n \le 4 keine Lösungen existieren, da der Springer immer in einer Sackgasse landet, egal von wo er startet. Sie können dies auch in dem unten verlinktem Java Programm austesten.

Einen kurzen Algorithmus, zur Lösung des Springerpoblems mit der Warnsdorff Heuristik, finden Sie in diesem Java Programm und ebenfalls ist dieses Applet zu empfehlen, wenn man selbst einen Weg für das Springerproblem finden möchte und um den Weg vielleicht besser nachvollziehen zu können.

Lokale Suche

Verzweigen und Begrenzen

Greedy-Heuristiken

Hill climbing

Threshold accepting

Simulated annealing

Video bei YouTube öffnen

Tabu-Suche

Sintflut-Algorithmus

Der Sintflutalgorithmus wurde 1993 von Gunter Dueck und Tobias Scheuer bei der Firma IBM in Heidelberg entwickelt. Er ist eine Weiterentwicklung bzw. Vereinfachung des weiter oben beschriebenen "Simulated Annealing"-Algorithmus und hat im Gegensatz zu den Treshold-accepting-Verfahren keinen Schwellwert der für jeden Schritt vorgegeben ist sondern eine globale untere Schranke die sich langsam aber stetig erhöht. Dabei spielt es keine Rolle, ob der nächste Schritt näher oder weiter entfernt von der Lösung gegenüber dem vorigen Schritt liegt, solange die globale Schranke nicht unterschritten wird. Im laufe des Prozesses wird dadurch die Anzahl der möglichen Schritte immer weiter eingeschränkt, bis keine Schritte mehr möglich sind und das gesuchte Optimum der Lösung gefunden ist.

Am besten lässt sich dies am Beispiel des Bergsteigers erklären, der

.

Fazit

Übungsaufgaben

Quellen

Literatur

[1] Christian Wagenknecht

Algorithmen und Komplexität,- Fachbuchverlag Leipzig, 2003.- ISBN 3-446-22314-2

[2] Doina Logofatu

Grundlegende Algorithmen mit Java - Vom Algorithmus zum fertigen Programm: Lern- und Arbeitsbuch für Informatiker und Mathematiker ,- Verlag Vieweg+Teubner, 2007.- ISBN 3834803693

Weblinks

^[1] Wikipedia Heuristik
^[2] Construction Heuristics
^{[3] fh-friedberg Sintflut}