Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSamstag, 15. August 2020 

Approximationsalgorithmus


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Ein Approximationsalgorithmus ist ein Algorithmus der für ein mathematisches Problem eine Näherungslösung liefert die möglichst an der exakten Lösung ist.

Die Güte eines Approximationsalgorithmus ist das Verhältnis von approximierter Lösung exakten Lösung gemessen in einer angemessenen Norm . Wenn ein Algorithmus immer die exakte liefert ist seine Güte 1 ansonsten größer. allgemeinen versteht man unter Approximationsgüte die absolute Approximationsgüte das ist die Güte die ein bei beliebiger Eingabe nicht überschreitet. Die asymptotische Approximationsgüte ist der Grenzwert der Approximationsgüte wenn Lösung gegen Unendlich geht.

Neben Algorithmen mit einem konstanten Approximationswert die immer um einen - möglicherweise gebrochenen Wert schlechter sind als das Optimum) gibt auch so genannte Approximationsschemata die es ermöglichen eine beliebig genaue der Lösung zu berechnen wobei die Laufzeit polynomiell in der Anzahl der Eingabevariablen (auch genannt) bleibt. In der theoretischen Informatik unterscheidet man folgende verschiedene Varianten:

FPAS
(manchmal auch FPTAS - fully polynomial time approximation scheme ) Der Algorithmus berechnet eine Approximation der (1+ε) deren Laufzeit polynomiell in der Länge Eingabe und 1/ε beschränkt ist.
PAS
Wie FPAS nur ist hier die nur polynomiell in der Länge der Eingabe
Super-PAS
Wie FPAS nur ist hier die polynomiell in der Länge der Eingabe und der Länge von ε (also in log(1/ε))




Bücher zum Thema Approximationsalgorithmus

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Approximationsg%FCte.html">Approximationsalgorithmus </a>