AuK/Näherungsverfahren 1 SS10

Wiki-Quelltext dieser Seite.

<language>Java</language>
=Einführung=

=Heuristiken=

==Begriff==

==Springerproblem==
[[Bild:Sipabrei_340px-Knight's_tour.svg.png|right|300px|Springerproblem]]

===Erläuterung des Springerproblems===

Vor mehr als 200 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...

===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===