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 finden durch geringfügiges variieren der Problemstellung oft ein korrektes Ergebnis.
* Auch [[Probabilistische Algorithmen 2]] sind ein guter Ansatz, um näherungsweise eine gute Lösung zu erhalten.
* Heuristiken sowie 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-->


===Heuristiken vs Probabilistische Algorithmen===

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