Approximationsalgorithmus - LinkFang.de





Approximationsalgorithmus


Ein Approximationsalgorithmus ist in der Informatik ein Algorithmus, der ein Optimierungsproblem näherungsweise löst.

Viele Optimierungsprobleme lassen sich mit exakten Algorithmen vermutlich nicht effizient lösen. Für solche Probleme kann es sinnvoll sein, wenigstens eine Lösung zu finden, die einer optimalen Lösung möglichst nahe kommt.

Güte von Approximationsalgorithmen

Es sei [math]S(x)[/math] der zu einer Eingabe [math]x[/math] gehörige Lösungsraum. Zu jeder möglichen Lösung [math]y \in S(x)[/math] sei [math]v(y)[/math] die Güte. Die Güte einer optimalen Lösung sei [math]v^*[/math]. Ein Approximationsalgorithmus sucht nun nach einer Lösung [math]y \in S(x)[/math], so dass [math]v(y)[/math] möglichst nah an [math]v^*[/math] liegt.

Die Güte eines Approximationsverfahrens ist definiert durch das Verhältnis von approximierter Lösung zur exakten Lösung. Die Güte einer Lösung [math]y\in S(x)[/math] wird bestimmt durch:

[math]r = \max \left\{\frac{v(y)}{v^*},\frac{v^*}{v(y)}\right\}[/math]

Diese Definition der Güte kann sowohl auf Minimierungs- wie auch auf Maximierungsprobleme angewandt werden. Es gilt immer [math]r \geq 1[/math]. Gilt [math]r = 1[/math], liefert der Algorithmus immer die optimale Lösung.

Klassen von Approximationsalgorithmen

Optimierungsprobleme werden in der Theoretischen Informatik in verschiedene Approximationsklassen unterschieden, je nachdem welcher Grad an Approximation möglich ist:

APX

Die Abkürzung APX steht für approximable und deutet an, dass das Optimierungsproblem, zumindest bis zu einem gewissen Grad, effizient approximierbar ist. Ein Problem liegt in der Klasse APX, wenn ein polynomieller Algorithmus existiert, der bei jeder zulässigen Eingabe [math]x[/math] eine Lösung mit einer Güte [math]\leq r[/math], mit [math]r[/math] konstant, liefert.

PTAS/PAS

PTAS oder PAS steht für polynomial time approximation scheme. Anders als bei der Klasse APX wird hier für jedes [math]\delta \in (0,1)[/math] gefordert, dass ein polynomialer Algorithmus existiert, der bei jeder zulässigen Eingabe eine Lösung mit einer Güte [math]r \leq 1+\delta[/math] liefert. Der Algorithmus muss also nicht nur für eine bestimmte Güte, sondern für jede Approximationsgüte effizient sein.

FPTAS

FPTAS steht für fully polynomial time approximation scheme. Hier wird gefordert, dass sich der Algorithmus nicht nur polynomiell zur Eingabe, sondern auch zur Güte der Approximation verhält. Dass es also zu jeder Eingabe [math]x[/math] und jedem [math]k \in \mathbb{N}[/math] eine Lösung mit der Güte [math]r \leq 1+1/k[/math] gibt, wobei der Algorithmus polynomiell in [math]x[/math] und [math]k[/math] ist.

Es gilt: [math]PO \subseteq FPTAS \subseteq PTAS \subseteq APX \subseteq NPO[/math]

Unter der Annahme [math]P \neq NP[/math] sind die obigen Inklusionsabbildungen echte Inklusionen. Das heißt, es gibt zum Beispiel mindestens ein Optimierungsproblem, das in der Klasse PTAS liegt, aber nicht in der Klasse FPTAS. Unter dieser Annahme existiert auch mindestens ein Optimierungsproblem, das nicht in APX liegt. Dies lässt sich unter der Annahme [math]P \subsetneq NP[/math] zum Beispiel für das Cliquenproblem zeigen.

Literatur

  • Rolf Wanka: Approximationsalgorithmen - Eine Einführung, Teubner, Wiesbaden, 2006, ISBN 3-519-00444-5
  • Klaus Jansen, Marian Margraf: Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, Berlin, New York, 2008, ISBN 978-3-11-020316-5

Siehe auch


Kategorien: Optimierungsalgorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Approximationsalgorithmus (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.