AuK/Näherungsverfahren 1 SS11

Wiki-Quelltext dieser Seite.

==Approximation des Optimums== <!--Die Überschriften ab level 2(==Text==) benutzen(machen die anderen auch so-->

In der Praxis interessiert man sich für NP-vollständige Probleme, für denen es keine effizienten Algorithmen gibt. Für eine sinnvolle Lösung sind deshalb "Ersatzalgorithmen" sinnvoll, die sich durch eine Modifizierung des Problems gefunden werden können. Das geschieht z.B. durch das Verstärken oder Abschwächen von Nebenbedingungen oder durch das Einschränken auf Teilprobleme.
Das Ergebnis solcher Näherungsalgorithmen sollte sich möglichst geringfügig von der exakten Lösung abweichen.

==Heuristik==

Der Begriff '''Heuristik''' kommt aus dem griechischen "heuriskein" und bedeutet "auffinden" oder "entdecken". Eine Heuristik ist eine Methode, mit der man ein Problem sinnvoll lösen kann, die aber nicht immer funktioniert.
Es werden aus einer Vielzahl von Möglichkeiten eine gewisse Anzahl von Möglichkeiten herausgefiltert.
Ein Bauer sagt zum Beispiel am Abend schlechtes Wetter für den nächsten Tag vorher und mach am nächsten Tag nur die Aufgaben, die bei schlechtem Wetter möglich sind. Dabei wendet er globale und individuelle Erfahrungsgrundsätze an. 

Der Unterschied zwischen Heuristiken und probabilistische Algorithmen besteht darin, dass bei probabilistischen Algorithmen Entscheidungen durch Zufall getroffen werden. 

Heuristiken eignen sich vermutlich für NP-vollständige Probleme.

===Heuristiken für das Springerproblem===

Das ''Springerproblem'', auch das Problem des Rösselsprungs genannt, wurde vor über 200 Jahren von Euler folgendermaßen formuliert:

''"Gibt es für einen Springer einen Weg, der jedes Feld eines <math>n \times  n</math>-Schachbrettes genau einmal besucht?"''

Ein Springer ist eine Schachfigur, die sich von ihrem aktuellen Feld <math>A(x_A,y_A)</math> zu einem Feld <math>B(x_B,y_B)</math> bewegen kann. Dabei gilt entweder

<blockquote><math>|x_A - x_B|= 2</math> und <math>|y_A - y_B|= 1</math> oder</blockquote>

<blockquote><math>|x_A - x_B|= 1</math> und <math>|y_A - y_B|= 2</math> ,</blockquote>

"Im Klartext" bedeutet dies, dass der Springer in einem Zug in jede Richtung zwei Felder vorwärts und ein Feld seitwärts bewegt werden kann. Die Koordinaten können dabei Werte natürlicher Zahlen aus [<math>1,n</math>] annehmen.

Die Anzahl der erreichbaren Felder variiert dabei, so kann ein Springer in einer Ecke des Brettes lediglich zwei mögliche Züge ausführen, während ein Springer in der Mitte des Brettes ganze acht Zugmöglichkeiten besitzt.

Zu beachten ist, dass es sich bei dem Springerproblem um ein Entscheidungsproblem handelt. Das bedeutet, es wird nicht nach einem konkreten Weg gefragt, sondern lediglich nach der Existenz eines solchen. Auch das Startfeld des Springers ist nicht festgelegt, das heißt, dass auf jedem der <math>n^2</math> Felder begonnen werden kann. Dies ist wichtig, da im Allgemeinen nicht für jedes Startfeld ein (vollständiger) Springerweg besteht.