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.

==Heurisitk==

===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.
<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
===Hamilton-Weg-Problem===
Das Springerproblem ist ein spezielles Hamilton-Weg-Problem welches nicht NP-vollständig ist.

==Lokale Suche==

Die bereits behandelten Verfahren "branch and bound" und "Greedy" können unter bestimmten Voraussetzungen auch für Näherungen (Approximationen) verwendet werden.

===Verzweigen und Begrenzen===

Hier 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===


====Nearest neighbour heuristic====
====Farthest insertion====
====Random insertion====
====Best insertion====

===Hill climbing===

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

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