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=

Die [[AuK/P-NP-Problem_SS10|P-NP-Problem]] und [[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".
==Springerproblem==


[[Bild:Sipabrei_Sprungmoeglichkeiten.gif|right|300px|frame|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 <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.

...

...

...

===Lösung mit Backtracking===

Der Naive Algorithmus...
[[Bild:Sipabrei_340px-Knight's_tour.svg.png|right|300px|Springerproblem]]
===Warnsdorff Heuristik=== 


Einen kurzen Algorithmus, zur Lösung des Springerpoblems mit der Warnsdorff Heuristik, finden Sie [[AuK/Näherungsverfahren_1_SS10/Java1|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==
<sup>[1]</sup> [http://de.wikipedia.org/wiki/Heuristik wikipedia Heuristik]<br>