AuK/Näherungsverfahren 1 SS10

Wiki-Quelltext dieser Seite.

<language>Java</language>
'''Autoren:'''
#Patrick Breite  ([mailto:sipabrei@stud.hs-zigr.de sipabrei@stud.hs-zigr.de])
#Marcel Mücke  ([mailto:simamuec@stud.hs-zigr.de 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:
<br>1. [[AuK/P-NP-Problem_SS10|P-NP-Problem]]
<br>2. [[AuK/Probabilistische_Algorithmen_SS10|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 <math>A(x_1 , y_1)</math> zu einem Feld <math>B(x_2 , y_2)</math> bewegt werden kann, wobei zu beachten ist das entweder 

<math>|x_1 - x_2| = 1</math> und <math>|y_1 - y_2| = 2</math>

oder

<math>|x_1 - x_2| = 2</math> und <math>|y_1 - y_2| = 1</math>   

für die Bewegungen des Springers gelten muss.

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

[[Bild:Sipabrei_Sprungmoeglichkeiten.gif|middle|200px|mögliche Züge für einen Springer]]

===Lösung mit Backtracking===


[[Bild:Sipabrei_340px-Knight's_tour.svg.png|right|300px|Springerproblem]]
Lange Zeit war für die Lösung des sogenannten ''Rösselsprungs'' nur der Naive Algorithmus mit Backtracking bekannt, wodurch ein Exponentieller Aufwand entsteht

===Warnsdorff Heuristik=== 


Einen kurzen Algorithmus, zur Lösung des Springerpoblems mit der Warnsdorff Heuristik, finden Sie [[AuK/Näherungsverfahren_1_SS10/Java1|hier]] und ebenfalls ist [http://web.telia.com/~u85905224/knight/dWarnsd.htm|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===
=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==
<sup>[1]</sup> [http://de.wikipedia.org/wiki/Heuristik wikipedia Heuristik]<br>