Approximation des Optimums

In der Praxis interessiert man sich für NP-vollständige Probleme, für denen es keine effizienten Algorithmen gibt. Für eine sinnvolle Lösung sind deshalb "Ersatzalgorithmen" sinnvoll, die sich durch eine Modifizierung des Problems gefunden werden können. Das geschieht z.B. durch das Verstärken oder Abschwächen von Nebenbedingungen oder durch das Einschränken auf Teilprobleme. Das Ergebnis solcher Näherungsalgorithmen sollte sich möglichst geringfügig von der exakten Lösung abweichen.

Heuristik

Der Begriff Heuristik kommt aus dem griechischen "heuriskein" und bedeutet "auffinden" oder "entdecken". Eine Heuristik ist eine Methode, mit der man ein Problem sinnvoll lösen kann, die aber nicht immer funktioniert. Es werden aus einer Vielzahl von Möglichkeiten eine gewisse Anzahl von Möglichkeiten herausgefiltert. Ein Bauer sagt zum Beispiel am Abend schlechtes Wetter für den nächsten Tag vorher und mach am nächsten Tag nur die Aufgaben, die bei schlechtem Wetter möglich sind. Dabei wendet er globale und individuelle Erfahrungsgrundsätze an.

Der Unterschied zwischen Heuristiken und probabilistische Algorithmen besteht darin, dass bei probabilistischen Algorithmen Entscheidungen durch Zufall getroffen werden.

Heuristiken eignen sich vermutlich für NP-vollständige Probleme.