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. P-NP-Problem
2. Probabilistische Algorithmen

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

Sie 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="4c0e16e3c7d1f"></eval>

Einen kurzen Algorithmus, zur Lösung des Springerpoblems mit der Warnsdorff Heuristik, finden Sie hier und ebenfalls ist dieses Applet zu empfehlen, wenn man selbst einen Weg für das Springerproblem finden möchte.

Lokale Suche

Verzweigen und Begrenzen

Greedy-Heuristiken

Hill climbing

Threshold accepting

Simulated annealing

Tabu-Suche

Sintflut-Algorithmus

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