Optimierungs-Problem

Optimierungs-Problem

Bei einem Optimierungsproblem ist ein Lösungsraum (Menge von möglichen Lösungen) Ω und eine Bewertungsfunktion (auch Ziel- oder Fitnessfunktion) f: \Omega \rightarrow \mathbb{R} gegeben. Man will eine Lösung x \in \Omega mit möglichst großem Wert f(x) finden, oder Aussagen über die Werte der Lösungen machen.

In diesem Fall läge ein Maximierungsproblem vor, bei einem Minimierungsproblem sind Lösungen x mit möglichst kleinem f(x) gesucht, aber dieser Fall lässt sich durch einfaches Negieren von f auf den vorigen zurückführen.

Man unterscheidet drei Problemstellungen:

  • Entscheidungsprobleme, bei denen zusätzlich ein Grenzwert g \in \mathbb{R} gegeben ist, und ermittelt werden soll, ob es ein x \in \Omega gibt mit f(x) \geq g.
  • eigentliche Optimierungsprobleme, bei denen man den Wert der besten Lösung wissen will, also  \max \{f(x) | x \in \Omega\} .
  • Suchprobleme, bei denen eine optimale Lösung  o \in \Omega gesucht ist, also so dass  f(o) = \max \{f(x) | x \in \Omega\} . Zumindest will man eine möglichst gute Lösung finden, falls das Ermitteln einer optimalen Lösung nicht praktikabel ist (Approximation).


In der Theoretischen Informatik meint man mit Optimierungsproblem in der Regel ein eigentliches Optimierungsproblem, bei dem also nur der bestmögliche Wert und keine Lösung selbst gesucht ist. Auch betrachtet man üblicherweise den Sonderfall einer diskreten Bewertungsfunktion f: \Omega \rightarrow \mathbb{N}, da dies meist keinen erheblichen Unterschied macht und man reelle Zahlen bzw. Gleitkommazahlen weniger gut handhaben kann.

Meistens betrachtet man in der Theoretischen Informatik aber Entscheidungsprobleme. Zu einem Optimierungsproblem lässt sich leicht ein Entscheidungsproblem erzeugen, indem man zur Problemstellung den Grenzwert g \in \mathbb{R} bzw. g \in \mathbb{N} hinzunimmt.

In der praktischen Anwendung hat man es meistens mit Suchproblemen zu tun, denn der Wert einer optimalen Lösung nützt einem ohne Kenntnis dieser Lösung in der Regel nichts. 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.

Siehe auch Optimierung (Mathematik), Evolutionärer Algorithmus


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • C.p. — Ceteris paribus (lateinisch: wobei die übrigen Dinge gleich sind) (Abk. c.p. oder cet. par. ) ist eine in Zusammenhang mit Experimenten gebrauchte Formulierung (auch Ceteris paribus Klausel genannt), die so viel bedeutet wie: „Unter der Annahme,… …   Deutsch Wikipedia

  • Cet. par. — Ceteris paribus (lateinisch: wobei die übrigen Dinge gleich sind) (Abk. c.p. oder cet. par. ) ist eine in Zusammenhang mit Experimenten gebrauchte Formulierung (auch Ceteris paribus Klausel genannt), die so viel bedeutet wie: „Unter der Annahme,… …   Deutsch Wikipedia

  • Ceteris-paribus-Klausel — Ceteris paribus (lateinisch: wobei die übrigen Dinge gleich sind) (Abk. c.p. oder cet. par. ) ist eine in Zusammenhang mit Experimenten gebrauchte Formulierung (auch Ceteris paribus Klausel genannt), die so viel bedeutet wie: „Unter der Annahme,… …   Deutsch Wikipedia

  • Ameisenalgorithmus — Bestimmte Verhaltensmuster der Ameisen bilden die Grundlage für Optimierungs Algorithmen, hier Dorylus) Ameisenalgorithmen gehören zu den Metaheuristiken für Verfahren der kombinatorischen Optimierung, die auf dem modellhaften Verhalten von… …   Deutsch Wikipedia

  • Komplexitätstheorie — Die Komplexitätstheorie als Teilgebiet der Theoretischen Informatik befasst sich mit der Komplexität von algorithmisch behandelbaren Problemen auf verschiedenen mathematisch definierten formalen Rechnermodellen. Die Komplexität von Algorithmen… …   Deutsch Wikipedia

  • D* — Der D* Algorithmus ist eine Erweiterung des A* Algorithmus und somit ein direkter Nachfahre des Dijkstra Algorithmus. Sowohl A* als auch der Dijkstra Algorithmus sind in ihrer Grundform unflexibel und können auf Veränderungen im Graphen während… …   Deutsch Wikipedia

  • D*-Algorithmus — Der D* Algorithmus ist eine Erweiterung des A* Algorithmus und somit ein direkter „Nachfahre“ des Dijkstra Algorithmus. Sowohl A* als auch der Dijkstra Algorithmus sind in ihrer Grundform unflexibel und können auf Veränderungen im Graphen während …   Deutsch Wikipedia

  • Kkt — Die Konvexe Optimierung ist ein Teilgebiet der mathematischen Optimierung. Es ist eine bestimmte Größe zu minimieren, die sogenannte Zielfunktion, welche von einem Parameter, welcher mit x bezeichnet wird, abhängt. Außerdem sind bestimmte… …   Deutsch Wikipedia

  • Konvexe Optimierung — Die Konvexe Optimierung ist ein Teilgebiet der mathematischen Optimierung. Es ist eine bestimmte Größe zu minimieren, die sogenannte Zielfunktion, welche von einem Parameter, welcher mit x bezeichnet wird, abhängt. Außerdem sind bestimmte… …   Deutsch Wikipedia

  • Kuhn-Tucker-Bedingungen — Die Konvexe Optimierung ist ein Teilgebiet der mathematischen Optimierung. Es ist eine bestimmte Größe zu minimieren, die sogenannte Zielfunktion, welche von einem Parameter, welcher mit x bezeichnet wird, abhängt. Außerdem sind bestimmte… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”