AuK/Näherungsverfahren 1 SS09

Wiki-Quelltext dieser Seite.

<!--TODO einleitung-->
==Approximation des Optimums==

===Ausgangssituation===
In der Praxis besteht oft großes Interesse an der Lösung von NP-vollständigen Problemen. Wie jedoch das [[P-NP-Problem]] zeigt muss davon ausgegangen werden, dass für NP-vollständige Probleme keine effizienten Algorithmen für deren Lösung existieren. Dieser Art von Problemen ist man jedoch nicht vollig hilflos ausgeliefert.

===Lösungsansatz===

* Sehr selten findet man "Ersatzalgorithmen". Sie liefern durch geringfügiges variieren der Problemstellung oft ein korrektes Ergebnis.
* Auch [[Probabilistische Algorithmen 2|probabilistische Algorithmen]] sind ein guter Ansatz, um näherungsweise eine gute Lösung zu erhalten.
* [[Näherungsverfahren 1#Heuristik|Heuristiken]] sowie [[Näherungsverfahren 1#Lokale Suche|lokale Suche]] sind ebenfalls Näherungsverfahren. Eine ausführliche Betrachtung dieser beiden folgt weiter unten.

==Heurisitken==

===Begriff===

[gr., Erfindungskunst]<br />
Erkenntnistheoretisches und methodisches Verfahren, durch Aufstellung oder Annahme von (unbewiesenen) Prinzipien und Regeln zu neuen Erkenntnissen zu gelangen.
<!--TODO Quellenangabe-->

Beispielsweise zählen [http://www.bauernregeln.net Bauernregeln] zu den Heuristiken.
<blockquote>''Bis 18. Juni die Schafskält nun dauert, dann die Wärme wieder lauert.''</blockquote>

Es gab lange Zeit keine Möglichkeit das Wetter zuverlässig vorherzusagen. Auch derzeit ist es nicht möglich für einen längeren Zeitraum eine exakte Vorhersage zu treffen. Die Bauern beobachteten das Wetter und stellten fest, dass auf ein bestimmtes Ereignis in der Regel ein bestimmtes anderes Ereignis folgt. Sie formulierten diese Beobachtung in einer Bauernregel und hatten von da an eine Empfehlung, um ihre Arbeit effizenter gestalten zu können. Die Erfolgsquote einer solchen Regel ist jedoch nicht vorhersehbar.<br />

Hier liegt auch der entscheidende Unterschied zu den [[Probabilistische Algorithmen 2|probabilistischen Algorithmen]], die eine Fehlerwahrscheinlichkeitbestimmung zulassen.

===Das Springerproblem===
<!--TODO[[Bild:Euler_1.jpg|Bildunterschrift]]-->
Das Springerproblem wurde Mitte des 18.Jh von Leonhard Euler formuliert. Es ist ein spezielles Hamilton-Weg-Problem, welches nicht NP-vollständig ist.
<blockquote>''Gibt es für einen Springer einen Weg, der jedes Feld eines n x n Schachbrettes genau einmal besucht?''</blockquote>
====Spielregeln====
Es wird lediglich nach der Existenz eines Weges gefragt und nicht nach der zurückgelegten Route. Das Startfeld kann frei gewählt werden.<br />
<!--TODO[[Bild:Demo.jpg]]-->
Die Zugregeln des Springers sind die aus dem Schach bekannten.
Der Springer darf:
* 2 Felder in vertikaler Richtung ziehen und 1 Feld in horizontaler Richtung oder
* 2 Felder in horizontaler Richtung und 1 Feld vertikaler Richtung und
* natürlich darf er das Spielfeld nicht verlassen
====Nichtheuristische Algorithmen====
Der naheliegendste Versuch das Problem zu lösen, ist der Einsatz von '''Backtracking'''. Der Algorithmus durchläuft jede mögliche Kombination und findet daher auch immer eine Lösung, sofern es diese überhaupt gibt. Backtracking scheitert jedoch in diesem Fall schon bei recht kleinen Schachbrettern (etwa ab Größe 10 x 10) am exponentiell wachsendem Zeitaufwand.

Eine Schülergruppe gelang es 1992 im Rahmen des Bundeswettstreits für Informatik einen vollständige Lösung des Springerproblems anzugeben. Der Conrad Algorithmus wurde nach Axel Conrad einem Mitglied der Gruppe benannt.

====Warnsdorff Heuristik====
H.C. Warnsdorff beschrieb um 1823 eine Heuristik, die sich aus der Beobachtung ableitet, dass häufig die Felder mit niedrigsten Anzahl an Folgefelder isoliert wurden. Gibt es von allen möglichen Folgefeldern eines mit nur einem Folgefeld muss es im nächsten Zug besucht werden, ansonsten entsteht eine Sackgasse. Man kann das Feld auch später noch besuchen, jedoch ist dann der Rückweg abgeschnitten. Er stellte folgende Regeln auf und hatte damit eine Näherungslösung gefunden die in O(n<sup>2</sup>) liegt:
* Ziehe auf das Feld mit der geringsten Anzahl möglicher Folgefeldern.
* Haben mehrere Felder die gleiche minimale Anzahl, so ziehe auf das zuerst bzw. zuletzt betrachtete Feld.
Vor einer Springertour muss festgelegt werden in welcher Reihenfolge die zu betrachtenden Felder ausgewählt werden.<br />

Da Warnsdorff alle Springertouren per Hand durchrechnen mußte, entging ihm offensichtlich, dass sein Verfahren nicht alle Sackgassen meidet.

====Modifikation des Springerproblems====

====Modifikation der Warnsdorff Heuristik====

==Lokale Suche==

Die bereits behandelten Verfahren "branch and bound" und "Greedy" können unter bestimmten Voraussetzungen auch für Näherungen (Approximationen) verwendet werden. Die Vorgehensweise für diese Verfahren wird in den nächsten Abschnitten erklärt.


===Verzweigen und Begrenzen===

*Beim Verzweigen und Begrenzen (branch and bound) wird die eigentlich erforderliche Schrankenfunktion durch eine grobe Schätzfunktion ersetzt. Dadurch entfällt die Berechnung für die Schranke (bound). Man akzeptiert keine Schranke ermittelt zu haben, aber die entstandenen Näherungswerte für das Optimum sind trotzdem zufriedenstellend.


===Greedy Heuristiken===

*Greedy-Heuristiken streben stets nach einer lokalen Verbesserung und sind dafür weder bereit eine vorübergehende Verschlechterung hinzunehmen, noch eine Entscheidung zu revidieren. 
*Wenn man die Greedy-Heuristiken zur näherungsweisen Lösung des Rundreiseproblems anwendet, dann wird jeweils der Knoten als nächstes integriert der den größten Gewinn realisiert also in diesem Fall eine kürzere Rundreise beschert.


====Nearest neighbour heuristic====

*Bei dieser Methode wählt man einen beliebigen Startpunkt auf der Rundreise und bindet dann jeweils den Knoten mit dem minimalsten Abstand zum aktuellen Knoten ein. Diese Variante ist natürlich sehr einfach, aber die entstandenen Ergebnisse sind nicht wirklich gut. Hier ein Link zum Applet was die Methode grafisch darstellt:<br>[http://www-e.uni-magdeburg.de/mertens/TSP/node2.html#SECTION00021000000000000000 Applet - nearest neighbour heuristic (Mertens)]


====Farthest insertion====

*Hier wird die Tour um jeweils den Knoten, dessen Minimalabstand zu einem bereits auf der Route vorhandenen Knoten maximal ist, erweitert. Hat den jeweiligen Knoten ermittelt wird er so in die Rundreise integriert das Streckenzuwachs minimal ist.
*Dafür gibt es verschiedene Ansatzmöglichkeiten:
#Wie im Buch "Algorithmen und Komplexität" von Prof. Wagenknecht beschrieben, beginnt man mit den jeweils am engsten zusammenliegenden Knoten und erweitert die Tour dann wie oben beschrieben.
#Herr Mertens von der Universität Magdeburg beschreibt auf seiner Website eine andere Vorgehensweise.
#* Man beginnt mit den Knoten die das größte Dreieck aufspannen und integriert dann die restlichen Knoten oder
#* Man benutzt eine "Konvexe Hülle". Es wird eine Verbindung durch alle am äußersten Rand liegenden Knoten hergestellt, so dass man eine Art Hülle um alle noch nicht integrierten Knoten erhält. Anschließend bindet man diese Knoten wie gehabt ein.
#*Eine Beschreibung und ein schönes Applet was diese Vorgehensweise verdeutlicht findet man unter folgendem Link:<br>[http://www-e.uni-magdeburg.de/mertens/TSP/node2.html#SECTION00022000000000000000 Applet - farthest insertion (Mertens)]
*Diese Anwendung führt zu guten Werten.


====Random insertion====

*Die random insertion führt zu ebenfalls guten Werten.
*Die Vorgehensweise ist ähnlich der farthest insertion mit dem Unterschied das die Knoten zufällig ausgewählt werden. Dadurch wird die Zeit für die Ermittlung des Knoten, dessen Minimalabstand am maximalsten ist, eingespart.

 
====Best insertion====

*Man hat herausgefunden das größere Schritte besser sind als kleine.
*Anstelle beim TSP die Auswirkungen kleinerer Veränderungen zu betrachten, wählt man große.
*Ähnlich wie bei einem Bombenabwurf zerstört man in einem kreisförmigen Gebiet alle Städte, baut sie nacheinander wieder auf und integriert sie mittels Farthest-insertion-Methode.
*Die Rundweglänge in diesem Ruin-and-create-Bereich ist danach meist kürzer als vorher.


===Hill climbing===

*auch local search genannt
*Es stellt eine einfache lokale Verbesserungsstrategie dar, die gelegentlich ein lokales anstelle des globalen Optimums ermittelt
*Zum Beispiel ein Bergsteiger der einen Gipfel erklimmmen will nimmt an jeder Gabelung den Weg mit dem höchsten Anstieg. Wenn er am Ende angekommen ist kann es durchaus passiert sein das er auf einem Nebengipfel gelandet ist.
*Auf das Rundreiseproblem angewandt werden in der fertigen Rundreise zufällig 2 nicht benachbarte Knoten ausgewählt und zu einem neuen Minimum geführt. Das gelingt wenn die Entfernungsmatrix symmetrisch ist und die die Rundreise dadurch nicht in 2 Komponenten zerfällt.
*Im Unterschied zu Greedy-Verfahren erwartet hill climbing einen Lösungsvorschlag der durch Modifikation (hoffentlich) verbessert wird.
*Um einen ersten Lösungsvorschlag bereitzustellen ist es sinnvoll zuerst Greedy anzuwenden.<br>
----
<br>
*Diese einfachen Heuristiken werden im täglichen Leben verwendet und entsprechen unserer Intuition. Bei vielen Planungen, z.B. Kofferpacken beginnnen wir immer mit den wichtigsten, den größten Teilen. Danach folgen weniger wichtige bis man auf unüberwindliche Verpackungsschwierigkeiten stößt.
*Dennoch sind diese Heuristiken in vielen Fällen erfolgreich. Aber es gibt noch bessere Verfahren.


===Threshold accepting===


===Simulated annealing===
===Tabu-Suche===
===Sintflut-Algorithmus===

==Links==
[http://www-e.uni-magdeburg.de/mertens/TSP/index.html TSP/Mertens]<br />
[[AuK|Startseite]]