Näherungsverfahren 1 SS09

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

TSP/Mertens AuK