AuK/Näherungsverfahren 1 WS13-14

Wiki-Quelltext dieser Seite.

==Einleitung==
===Motivation===
Besonders in der Praxis sind NP-vollständige Probleme, für die es keine effizienten Algorithmen gibt, von großem Interesse. Dies zeigte sich bei der Diskussion des P-NP-Problems.
Durch Modifizierung des Problems können sogenannte "Ersatzalgorithmen" gefunden werden. Dies geschieht durch Verstärken oder Abschwächen von Nebenbedingungen oder durch das Einschränken auf Teilprobleme. Man bedient  sich also bestimmter Heuristiken, die zumindestens approximative (näherungsweise) Lösungen bieten. Doch es muss auch dafür gesorgt sein dass die Abweichung des Resultats von der unbekannten exakten Lösung möglichst gering ist.

===Heuristiken===
Heuristik stammt aus dem Griechischen und ist von dem Wort "heuriskien" abgeleitet und bedeutet so viel wie "(auf)-finden" bzw. "entdecken". Es handelt sich dabei um ein Verfahren mit dem man ein Problem sinnvoll löse kann, für das jedoch nicht garantiert werden kann das es zu 100% funktioniert. Bei diesem Verfahren wird aus einer Vielzahl von Möglichkeiten eine Gewissen Anzahl heraus gefiltert.  Die sogenannte Brute-Force-Methode ist das Gegenteil zu Heuristiken.

== Heuristiken für das Springerproblem ==
Ausgedacht wurde es vor langer Zeit, vor über 200 Jahren, genauer im Jahre 1758, und zwar von dem Schweizer Leonhard Euler.
Das Springerproblem ist ein kombinatorisches Problem, das darin besteht, für einen Springer auf einem leeren nxn- Schachbrett eine Route zu finden, auf der dieser jedes Feld genau einmal besucht wird. Eine Springertour heißt geschlossen, wenn das Endfeld des Springers einen Springerzug vom Startfeld entfernt ist.
Ein Springer ist eine Schachfigur, die sich von ihrem aktuellen Feld <math>A(x_1 , y_1)</math> zu einem Feld <math>B(x_2 , y_2)</math>) bewegen kann. Dabei muss beachtet werden das:

<math>|x_1 - x_2| = 1</math> und <math>|y_1 - y_2| = 2</math>

bzw.

<math>|x_1 - x_2| = 2</math> und <math>|y_1 - y_2| = 1</math>  


Das bedeutet der Springer kann 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 [1,n] annehmen.
Abhängig von der Position des Springers auf dem Spielfeld ist die Anzahl der erreichbaren Felder. 
Ein Springer in der Ecke des Spielfeldes hat zwei  Möglichkeit sich zu bewegen
Hingegen ein Springer in der Mitte des Spielfeldes acht Zugmöglichkeiten besitzt.

[[Bild:S3dobitt_Knightstour2.gif|thumb|Beispielsösung für das Springerproblem]]

== Lokale Suche ==
Unter bestimmten Voraussetzungen  können die bereits vorgestellten Verfahren  „Verzweigen und Begrenzen“ ,  „Greedy“ und noch nicht vorgestellte „Hill Climbing“ auch  für Nährungen verwendet werden. 

===Verzweigen und Begrenzen===
Beim Verzweigen und Begrenzen  wird die eigentliche Schrankenfunktion nicht mehr berechnet sondern durch eine Schätzfunktion ersetzt.  Das bedeutet das die Bound Berechnung entfällt und es wird akzeptiert das keine Schranke berechnet wurde. 
Das Ergebnis wird dadurch, dass es sich um ein Näherungsalgorithmus handelt, vom optimal Ergebnis abweichen, jedoch kann man davon ausgehen das Ergebnis in den meisten Fällen zufriedenstellend ist da diese Abweichungen nur minimal.

===Greedy Heuristiken===
Während das bereits kennen gelernte Greedy-Verfahren eine exakte Lösung bietet, wird bei der Greedy Heuristik nach einer lokalen Verbesserung gestrebt.  Dafür werden weder vorübergehende Verschlechterungen akzeptiert, noch Entscheidungen zurück genommen.
Wird eine Greedy-Heuristik zur approximativen Lösung eines TSP verwendet, heisst das nichts anderes als den gewinnträchtigsten Knoten als nächsten in die Rundreise einzubinden um eine möglichst kurze Rundreise zu gewährleisten. Das Rundreiseproblem gehört in die Kategorie der NP-vollständigen Problemen. Für solche Probleme ist kein effizienter Algorithmus bekannt ist  (Im Folgenden werden nun 4 verschiedene Herangehensweisen erklärt)

====Nearest neighbour heuristic====
Diese Herangehensweise ist eine recht kurzsichtige Methode.
Sie startet bei einem zufällig gewählten Knoten und wählt dann als nächsten Knoten, der den aktuellem Standort am nächsten ist. Diese Heuristik arbeitet in Polynomzeit <math>\mathcal{O}(n^2)</math>. Aber die entstanden Ergebnisse sind nicht wirklich zufrieden stellend.

====Farthest insertion====
Hier gibt es zwei Möglichkeiten: 
*Man startet bei den jeweils engsten zusammenliegenden Knoten und erweitert die Rundreise um jeweils den Knoten, dessen Minimalabstand  zu einem bereits auf der Route vorhanden Knoten maximal ist.
*Man benutzt eine „konvexe Hülle“, bei  der  alle am äußeren Rand liegenden Knoten verbunden werden. So entsteht eine Hülle um die noch nicht integrierten Knoten welche dann wie gehabt eingebunden werden. Die entstanden Ergebnisse sind zufriedenstellend.

====Random insertion====
Hier wird ein unbenutzter Knoten zufällig ausgewählt und so in die Rundreise integriert, dass die Rundreiselänge minimal wird.

====Best insertion====
Mittlerweile hat man herausgefunden das große Schritte besser sind als kleine, d.h. beim TSP werden anstatt kleine Veränderungen zu betrachtet, möglichst große gewählt.
Hier zerstört man die Städte, die im Kreis stehen und baut sie dann so wieder auf, dass man sie mittels farthest insertion in die Rundreise integriert. In diesem Bereich ist die Rundweglänge kürzer als zuvor.

===Hill Climbing===
===Threshold accepting===
===Simulatet annealing===
===Tabu-Suche===
===Der Sinflut-Algorithmus===

=Übungen=
=Literatur=
Christian Wagenknecht ''Algorithmen und Komplexität.'' Fachbuchverlag Leipzig, 2003, ISBN 3-446-22314-2, Seite 153-163