Näherungsverfahren 1 SS10
Inhaltsverzeichnis |
Autoren:
- Patrick Breite (sipabrei@stud.hs-zigr.de)
- 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 einspringers zu erkennen.
mögliche Züge für einen Springer
Lösung mit Backtracking
Der Naive Algorithmus...
Warnsdorff Heuristik
Einen kurzen Algorithmus, zur Lösung des Springerpoblems mit der Warnsdorff Heuristik, finden Sie hier und ebenfalls ist 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
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