Optimierungsproblem

Als Optimierungsproblem bezeichnet man in der Informatik das Problem zu einer Eingabe den Wert einer bestmöglichen Lösung zu finden, d.h. zu einem vorgegebenen Problem gibt es verschiedene Lösungen, denen reelle Zahlen zugeordnet sind. Gesucht ist eine Lösung, der eine möglichst hohe (Maximierungsproblem) bzw. möglichst kleine (Minimierungsproblem) Zahl zugeordnet ist.

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.