Optimierungsproblem
Als Optimierungsproblem bezeichnet man in der Theoretischen Informatik ein Problem, zu dem es aus einer Menge möglicher Lösungen eine bestmögliche Lösung zu finden gilt. Die Qualität jeder potentiellen Lösung zu einer Probleminstanz wird dabei durch ein Maß bewertet, das der Lösung eine (i.d.R. relle) Zahl zuordnet. Je nachdem, ob es sich um ein Minimierungs- oder Maximierungsproblem handelt, ist eine Lösung mit minimalem bzw. maximalem Wert bzgl. des Maßes gesucht. Eine solche Lösung wird auch als optimale Lösung bezeichnet.Zu einem Optimierungsproblem läßt sich leicht ein Entscheidungsproblem kreieren, indem man zur Eingabe noch eine Zahl als Begrenzung hinzunimmt und fragt, ob eine Lösung existiert, deren Wert kleiner (bzw. größer) als diese Zahl 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 Minimierungs- und Maximierungsproblem genauer vom Minimierungs- oder Maximierungsalgorithmus. Einen Algorithmus, der ein Optimierungsproblem näherungsweise löst, nennt man Approximationsalgorithmus.