| |
|
Zu einem Optimierungsproblem läßt sich leicht ein Entscheidungsproblem kreieren, indem man zur Eingabe noch eine Zahl hinzunimmt und fragt, ob es eine Lösung gibt, der ein Wert größer (bzw. kleiner) als diese Zahl zugeordnet ist.
Das Problem eine bestmögliche Lösung zu finden bezeichnet man oft als Suchproblem.
Einen Algorithmus, der ein Optimierungsproblem löst, nennt man Optimierungsalgorithmus. Analog spricht man beim Maximierungs- und Minimierungsproblem genauer vom Maximierungs- oder Minimierungsalgorithmus. Einen Algorithmus, der ein Optimierungsproblem näherungsweise löst, nennt man Approximationsalgorithmus.