=

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]
Erkenntnistheoretisches und methodisches Verfahren, durch Aufstellung oder Annahme von (unbewiesenen) Prinzipien und Regeln zu neuen Erkenntnissen zu gelangen.

===Heuristiken vs Probabilistische Algorithmen

Links

TSP/Mertens AuK