Näherungsverfahren 1 SS10
Aus ProgrammingWiki
Archivierte Version vom 2010-06-06T19:49:56+00:00. Aktuelle Version
Inhaltsverzeichnis |
Autoren:
- Patrick Breite (sipabrei@stud.hs-zigr.de)
- Marcel Mücke (simamuec@stud.hs-zigr.de)
Einführung
Heuristiken
Begriff
Springerproblem
mögliche Züge für einen Springer
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 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.