imported>Aka: Tippfehler entfernt

2021-11-15T19:14:11Z

Neue Seite

Ein '''Approximationsalgorithmus''' (oder auch '''Näherungsalgorithmus''') ist in der [[Informatik]] ein [[Algorithmus]], der ein [[Optimierungsproblem]] näherungsweise löst.

Viele Optimierungsprobleme lassen sich mit exakten Algorithmen [[P-NP-Problem|vermutlich]] nicht [[Effizienz (Informatik)|effizient]] lösen. Für solche Probleme kann es sinnvoll sein, wenigstens eine Lösung zu finden, die einer optimalen Lösung möglichst nahekommt.
Als Maß für die Bewertung von Approximationsalgorithmen benutzt man die sogenannte [[Güte von Approximationsalgorithmen|Güte des Algorithmus]].

== Klassen von Approximationsalgorithmen ==
Optimierungsprobleme werden in der [[Theoretische Informatik|Theoretischen Informatik]] in verschiedene Approximationsklassen unterschieden, je nachdem welcher Grad an Approximation möglich ist:

=== APX ===
Die Abkürzung ''APX'' steht für '''''ap'''pro'''x'''imable'' und deutet an, dass das Optimierungsproblem, zumindest bis zu einem gewissen Grad, effizient approximierbar ist.
Ein Problem liegt in der Klasse ''APX'', wenn eine Zahl <math>r</math> und ein [[Polynomialzeit|polynomieller]] Algorithmus, der bei jeder zulässigen Eingabe <math>I</math> eine Lösung mit einer Güte <math>\leq r</math> liefert, existieren.

=== PTAS/PAS ===
''PTAS'' oder ''PAS'' steht für '''''p'''olynomial '''t'''ime '''a'''pproximation '''s'''cheme''. 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 '''''f'''ully '''p'''olynomial '''t'''ime '''a'''pproximation '''s'''cheme''. Hier wird gefordert, dass sich der Algorithmus nicht nur polynomiell zur Eingabe, sondern auch zur Güte der Approximation verhält; Dass er also zu jeder Eingabe <math>I</math> und jedem <math>k \in \mathbb{N}</math> eine Lösung mit der Güte <math>r \leq 1+1/k</math> ausgibt und seine Laufzeit 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 [[Inklusionsabbildung]]en 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.

Sei <math>\Pi</math> ein Optimierungsproblem, dessen Zielfunktion <math>v\colon S(I) \to \mathbb{N}</math> für alle Instanzen <math>I</math> ganzzahlig ist.
Falls es ein Polynom <math>p</math> mit <math>opt(I)<p(|I|,maxnr(I))</math> für jede Instanz <math>I</math> gibt, dann folgt aus der Existenz eines FPTAS für <math>\Pi</math> die Existenz eines [[pseudopolynomiell]]en Algorithmus für <math>\Pi</math>.
Hierbei ist <math>opt(I)</math> die optimale Lösung für die Instanz <math>I</math> und <math>maxnr(I)</math> der maximale Wert einer Variable von <math>I</math>.

Da [[NP-Vollständigkeit#Starke NP-Vollständigkeit|stark NP-vollständige]] Probleme keinen pseudopolynomiellen Algorithmus haben (falls <math>P \neq NP</math>), besitzen diese daher kein FPTAS.

== Siehe auch ==
* [[Heuristik]]
* [[Iteration]]

== 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

[[Kategorie:Optimierungsalgorithmus]]

Approximationsalgorithmus - Versionsgeschichte

imported>Aka: Tippfehler entfernt