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

Springerproblem

mögliche Züge für einen Springer

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.

...

...

...

Lösung mit Backtracking

Der Naive Algorithmus...

Warnsdorff Heuristik

Einen kurzen Algorithmus, zur Lösung des Springerpoblems mit der Warnsdorff Heuristik, finden Sie hier.

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

Weblinks

^[1] wikipedia Heuristik