Näherungsverfahren 1 SS09
Inhaltsverzeichnis |
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 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.
Beispielsweise zählen Bauernregeln zu den Heuristiken.
Bis 18. Juni die Schafskält nun dauert, dann die Wärme wieder lauert.
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 anderes folgt. Sie formulierten diese Beobachtung in einer Bauernregel und hatten von da an einen Anhaltspunkt, um ihre Arbeit effizenter zu gestalten.