Optimierungsproblem
aus Wikipedia, der freien Enzyklopädie
Als Optimierungsproblem bezeichnet man in der Theoretischen Informatik ein Problem, das nach der Qualität einer bestmöglichen Lösung aus einer Menge von potentiellen Lösungen fragt. Die Qualität jeder potentiellen Lösung zu einer Probleminstanz wird dabei durch ein Maß bewertet, das der Lösung eine (meist reelle) Zahl zuordnet. Je nachdem, ob es sich um ein Minimierungs- oder Maximierungsproblem handelt, ist die Qualität einer Lösung mit minimalem bzw. maximalem Wert gesucht. Eine solche Qualität wird auch als Optimum bezeichnet.
Das Problem besteht nicht darin, eine optimale Lösung zu finden, sondern lediglich die Qualität einer optimalen Lösung. Ist nach einer optimalen Lösung gefragt, so bezeichnet man das Problem oft als Suchproblem. Natürlich kann das Problem aber auch dadurch gelöst werden, dass man zunächst eine optimale Lösung sucht und dann ihre Qualität als Ergebnis zurückgibt.
Zu einem Optimierungsproblem lässt 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.
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.
