Näherungsverfahren 1 SS10
Aus ProgrammingWiki
Archivierte Version vom 2010-06-06T14:36:12+00:00. Aktuelle Version
Inhaltsverzeichnis |
Einführung
Heuristiken
Begriff
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 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 ...
...
...
...
...
Lösung mit Backtracking
Der Naive Algorithmus...
Warnsdorff Heuristik
Einen kurzen Algorithmus, zur Lösung des Springerpoblems mit der Warnsdorff Heuristik, finden Sie hier.