AuK/Näherungsverfahren 1 SS09

Wiki-Quelltext dieser Seite.

==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 durchaus ein korrektes Ergebnis.
* Auch [[Probabilistische Algorithmen 2]] sind ein guter Ansatz, um näherungsweise eine gute Lösung zu erhalten.

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