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 S(x) der zu einer Eingabe x gehörige Lösungsraum. Zu jeder möglichen Lösung y \in S(x) sei v(y) die Güte. Die Güte einer optimalen Lösung sei v * . Ein Approximationsalgorithmus sucht nun nach einer Lösung y \in S(x), so dass v(y) möglichst nah an v * liegt.

Die Güte eines Approximationsverfahrens (sogenannte Approximationsgüte) wird durch die Performanz r des Algorithmus bestimmt. Sie ist definiert durch das Verhältnis von approximierter Lösung zur exakten Lösung, gemessen in einer angemessenen Norm. Die Performanz einer Lösung y\in S(x) wird bestimmt durch:

r = \min \left\{\frac{v(y)}{v^*},\frac{v^*}{v(y)}\right\}

Diese Definition der Performanz kann sowohl auf Minimierungs- wie auch auf Maximierungsprobleme angewandt werden. Es gilt immer r \leq 1.

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, effektiv approximierbar ist.
Ein Problem liegt in der Klasse APX, wenn eine Zahl \delta \in (0,1) und ein polynomialer Algorithmus existiert, der bei jeder zulässigen Eingabe x eine Lösung mit einer Performanz r \geq 1-\delta liefert.
PTAS/PAS
PTAS oder PAS steht für polynomial time approximation scheme. Anders als bei der Klasse APX wird hier für jedes \delta \in (0,1) gefordert, dass ein polynomialer Algorithmus existiert, der bei jeder zulässigen Eingabe eine Lösung mit einer Performanz r \geq 1-\delta liefert. Der Algorithmus muss also nicht nur für eine bestimmte Performanz, sondern für jede Performanz effektiv sein, der Existenzquantor wird durch einen Allquantor ersetzt.
FPTAS
FPTAS steht für fully polynomial time approximation scheme. Hier wird gefordert, dass sich der Algorithmus nicht nur polynomial zur Eingabe, sondern auch zur Güte der Approximation verhält. Dass es also zu jeder Eingabe x und jedem k \in \mathbb{N} eine Lösung mit der Performanz r \geq 1-1/k gibt, wobei der Algorithmus polynomial in x und k ist.

Es gilt: FPTAS \subseteq PTAS \subseteq APX

Unter der Annahme P \neq NP 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.

Fasst man die Inklusionskette etwas weiter:

{Optimierungsprobleme in P}\subseteq FPTAS \subseteq PTAS \subseteq APX \subseteq{Optimierungsprobleme in NP}

hieße das auch, dass es Optimierungsprobleme gibt, die nicht einmal in APX liegen. Dies lässt sich unter der Annahme P \subsetneq NP zum Beispiel für das Cliquenproblem zeigen.

Siehe auch


Wikimedia Foundation.

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

  • Approximationsalgorithmus —   [zu kirchenlat. approximare »sich nähern«], ein Algorithmus, der sich mit dem Auffinden einer Näherungslösung begnügt. Dabei soll die Abweichung der Näherungslösung von der optimalen Lösung vernachlässigbar gering ausfallen bezüglich der… …   Universal-Lexikon

  • Steiner Tree — Das Steinerbaumproblem (oft mit STEINER TREE notiert), ein nach dem Schweizer Mathematiker Jakob Steiner benanntes Problem der Graphentheorie, ist eine Verallgemeinerung des Problems des minimalen Spannbaums. Beim Steinerbaumproblem sucht man in… …   Deutsch Wikipedia

  • Steinerbaum — Das Steinerbaumproblem (oft mit STEINER TREE notiert), ein nach dem Schweizer Mathematiker Jakob Steiner benanntes Problem der Graphentheorie, ist eine Verallgemeinerung des Problems des minimalen Spannbaums. Beim Steinerbaumproblem sucht man in… …   Deutsch Wikipedia

  • Steinerbaum-Problem — Das Steinerbaumproblem (oft mit STEINER TREE notiert), ein nach dem Schweizer Mathematiker Jakob Steiner benanntes Problem der Graphentheorie, ist eine Verallgemeinerung des Problems des minimalen Spannbaums. Beim Steinerbaumproblem sucht man in… …   Deutsch Wikipedia

  • Algo — Al Chwarizmi, der Namensgeber des Algorithmus, auf einer sowjetischen Briefmarke anlässlich seines 1200 jährigen Geburtsjubiläums. Unter einem Algorithmus (auch Lösungsverfahren) versteht man eine genau definierte Handlungsvorschrift zur Lösung… …   Deutsch Wikipedia

  • Algorithmen — Al Chwarizmi, der Namensgeber des Algorithmus, auf einer sowjetischen Briefmarke anlässlich seines 1200 jährigen Geburtsjubiläums. Unter einem Algorithmus (auch Lösungsverfahren) versteht man eine genau definierte Handlungsvorschrift zur Lösung… …   Deutsch Wikipedia

  • Approximationsgüte — Ein Approximationsalgorithmus ist in der Informatik ein Algorithmus, der ein Optimierungsproblem näherungsweise löst. Viele Optimierungsprobleme lassen sich mit exakten Algorithmen nicht effizient lösen. Für solche Probleme kann es sinnvoll sein …   Deutsch Wikipedia

  • Approximationsschema — Ein Approximationsalgorithmus ist in der Informatik ein Algorithmus, der ein Optimierungsproblem näherungsweise löst. Viele Optimierungsprobleme lassen sich mit exakten Algorithmen nicht effizient lösen. Für solche Probleme kann es sinnvoll sein …   Deutsch Wikipedia

  • Approximationstheorie — Approximation (v. lat.: proximus, a, um = der, die, das Nächste) bezeichnet im mathematischen Sinn eine Näherung. Es gibt vor allem zwei Gründe, solche Näherungen zu untersuchen: Einmal könnte das Objekt des Interesses nur implizit, also als… …   Deutsch Wikipedia

  • Approximierbarkeit — Ein Approximationsalgorithmus ist in der Informatik ein Algorithmus, der ein Optimierungsproblem näherungsweise löst. Viele Optimierungsprobleme lassen sich mit exakten Algorithmen nicht effizient lösen. Für solche Probleme kann es sinnvoll sein …   Deutsch Wikipedia

Share the article and excerpts

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