Tilnærmelsesalgoritme

I datalogi er en tilnærmelsesalgoritme (eller tilnærmelsesalgoritme ) en algoritme, der omtrent løser et optimeringsproblem .

Mange optimeringsproblemer kan sandsynligvis ikke løses effektivt med nøjagtige algoritmer . For sådanne problemer kan det være fornuftigt at finde mindst en løsning, der kommer så tæt som muligt på en optimal løsning. Den såkaldte algoritmekvalitet bruges som et mål for evaluering af tilnærmelsesalgoritmer .

Klasser af tilnærmelsesalgoritmer

I teoretisk datalogi er optimeringsproblemer opdelt i forskellige tilnærmelsesklasser, afhængigt af hvilken tilnærmelsesgrad der er mulig:

APX

Forkortelsen APX står for ap pro x imable og indikerer, at optimeringen problemet kan tilnærmes effektivt, i det mindste i et vist omfang. Et problem ligger i klassen APX, når der findes et tal og en polynomalgoritme, der leverer en løsning med en kvalitet til alle tilladte input . ${\ displaystyle r}$${\ displaystyle I}$${\ displaystyle \ leq r}$

PTAS / PAS

PTAS eller PAS står for p olynomial t ime a pproximation s cheme . I modsætning til klassen APX kræves det her, at der findes en polynomalgoritme, der leverer en løsning med en kvalitet til alle tilladte input . Algoritmen skal derfor være effektiv ikke kun for en bestemt kvalitet, men for hver tilnærmelseskvalitet. ${\ displaystyle \ delta \ in (0,1)}$${\ displaystyle r \ leq 1+ \ delta}$

FPTAS

FPTAS står for f ully p olynomial t ime a pproximation s Cheme . Her kræves det, at algoritmen ikke kun opfører sig polynomisk over for input, men også til kvaliteten af ​​tilnærmelsen; At den udsender en løsning med kvaliteten for hver input og hver, og at dens driftstid er polynomisk i og . ${\ displaystyle I}$${\ displaystyle k \ in \ mathbb {N}}$${\ displaystyle r \ leq 1 + 1 / k}$${\ displaystyle x}$${\ displaystyle k}$

Følgende gælder: ${\ displaystyle PO \ subseteq FPTAS \ subseteq PTAS \ subseteq APX \ subseteq NPO}$

Under forudsætning af, at ovenstående inklusionskort er sande inklusioner. Dette betyder, at der for eksempel er mindst et optimeringsproblem, der er i PTAS- klassen, men ikke i FPTAS- klassen . Under denne antagelse er der også mindst et optimeringsproblem, der ikke findes i APX . Dette kan f.eks. Vises under antagelse for klikeproblemet . ${\ displaystyle P \ neq NP}$${\ displaystyle P \ subsetneq NP}$

Lad være et optimeringsproblem, hvis målfunktion er heltal for alle forekomster . Hvis der er et polynom med for hver forekomst , følger det af eksistensen af ​​en FPTAS for eksistensen af ​​en pseudopolynomealgoritme til . Her er den optimale løsning for forekomsten og den maksimale værdi for en variabel . ${\ displaystyle \ Pi}$${\ displaystyle v \ colon S (I) \ to \ mathbb {N}}$${\ displaystyle I}$${\ displaystyle p}$${\ displaystyle opt (I) <p (| I |, maxnr (I))}$${\ displaystyle I}$${\ displaystyle \ Pi}$${\ displaystyle \ Pi}$${\ displaystyle opt (I)}$${\ displaystyle I}$${\ displaystyle maxnr (I)}$${\ displaystyle I}$

Da stærkt NP-komplette problemer ikke har en pseudopolynomial algoritme (hvis ), har de derfor ikke en FPTAS. ${\ displaystyle P \ neq NP}$

Se også

• Heuristisk
• iteration

litteratur

• Rolf Wanka: Tilnærmelsesalgoritmer - En introduktion , Teubner, Wiesbaden, 2006, ISBN 3-519-00444-5
• Klaus Jansen, Marian Margraf: Approximate Algorithms and Non-Approximatability , de Gruyter, Berlin, New York, 2008, ISBN 978-3-11-020316-5