Optimierungsproblem - LinkFang.de





Optimierungsproblem


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

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

Man unterscheidet drei Problemstellungen:

  • Entscheidungsprobleme, bei denen zusätzlich ein Grenzwert [math]g \in \mathbb{R}[/math] gegeben ist, und ermittelt werden soll, ob es ein [math]x \in \Omega[/math] gibt mit [math]f(x) \geq g[/math].
  • eigentliche Optimierungsprobleme, bei denen man den Wert der besten Lösung wissen will, also [math] \max \{f(x) | x \in \Omega\} [/math].
  • Suchprobleme, bei denen eine optimale Lösung [math] o \in \Omega [/math] gesucht ist ([math] f(o) = \max \{f(x) | x \in \Omega\} [/math]), oder eine Lösung mit einer gegebenen Mindestqualität, also ein [math] o [/math] mit [math] f(o) \geq g [/math]. Oder man will einfach eine möglichst gute Lösung finden (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 [math]f: \Omega \rightarrow \mathbb{N}[/math], da dies meist keinen erheblichen Unterschied macht und man reelle Zahlen weniger gut handhaben kann, z. B. näherungsweise als Gleitkommazahlen.

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 [math]g \in \mathbb{R}[/math] bzw. [math]g \in \mathbb{N}[/math] hinzunimmt. Umgekehrt kann man für die meisten praktisch interessanten Probleme zeigen, dass ein Lösungsweg für das Entscheidungsproblem zu einer Lösung des entsprechenden Such- oder Optimierungsproblems modifiziert werden kann, die nicht entscheidend mehr Rechenzeit oder Speicherplatz benötigt.

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, bezeichnet man als Approximationsalgorithmus, oft aber auch etwas ungenau ebenfalls als Optimierungsalgorithmus.

Siehe auch

Weblinks


Kategorien: Optimierung

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Optimierungsproblem (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.