Approksimationsalgoritme

En tilnærmelsesalgoritme er en algoritme i operationsforskning , der bruges til at finde en omtrentlig løsning på et optimeringsproblem .

Konceptet med en tilnærmelsesalgoritme blev formaliseret i 1972 i et papir af Garey, Graham og Ullman [1] og senere af Johnson [2] . Approksimationsalgoritmer er ofte forbundet med NP-hårde problemer, da der næppe findes en effektiv polynomisk tidseksakt løsningsalgoritme for dem, så det giver mening at forsøge at finde en løsning, der er tæt på optimal. I modsætning til heuristiske algoritmer , som giver tilstrækkeligt gode løsninger på en acceptabel tid, giver tilnærmelsesalgoritmer en beviselig kvalitet af løsningen inden for forudbestemte tidsgrænser. Ideelt set giver tilnærmelsen en løsning, der adskiller sig fra den optimale med en lille faktor (f.eks. inden for 5%). Approksimationsalgoritmer bliver i stigende grad brugt til at løse problemer, for hvilke der kendes eksakte algoritmer, der kører i polynomiel tid, men kører i lang tid. Et typisk eksempel på en tilnærmelsesalgoritme er algoritmen til løsning af toppunktsdækslet i grafteori : find en udækket kant og tilføj begge dens toppunkter til toppunktsdækslet, og så videre, indtil alle er dækket. Det er klart, at den resulterende dækning kan være dobbelt så stor som den optimale. Denne løsning er en tilnærmelsesalgoritme med en konstant koefficient på 2.

NP-hårde problemer varierer meget i deres tilnærmelighed. Nogle, såsom bin-packing-problemet , kan tilnærmes med en hvilken som helst faktor større end 1 (denne familie af algoritmer kaldes Approximate Polynomial Time Scheme eller PTAS ). Andre problemer kan ikke tilnærmes med nogen konstant koefficient eller endda med en polynomiel koefficient (hvis P ≠ NP ), og blandt sådanne problemer er det maksimale klikproblem .

NP-hårde problemer kan ofte udtrykkes i form af heltalsprogrammering og løses nøjagtigt i eksponentiel tid . Mange eksponentielle algoritmer stammer fra at reducere et heltalsproblem til et lineært programmeringsproblem . [3]

Ikke alle tilnærmelsesalgoritmer er egnede til at løse praktiske problemer. Ofte bruger de CPU / LP / semi-definerede opgaver , komplekse datastrukturer eller sofistikerede programmeringsteknikker som underopgaver , hvilket fører til implementeringskompleksitet. Nogle tilnærmelsesalgoritmer har uacceptable køretider, selvom tiden er polynomiel (f.eks. O( n 2000 )). Ikke desto mindre forfølger studiet af selv sådanne urealistiske algoritmer ikke rent teoretiske mål, da det gør det muligt at forstå essensen af problemet. Et klassisk eksempel er den indledende PTAS-algoritme for det metriske rejsende sælgerproblem , ejet af Sanjiv Arora , som havde en næsten urealistisk køretid. Men inden for et år forfinede Arora ideen til en algoritme, der kørte i lineær tid. Sådanne algoritmer er også velegnede til opgaver, hvor driftstiden og omkostningerne kan begrundes. Disse opgaver omfatter Computational Biology , Financial Engineering , Transportation Planning og Inventory Management .

En anden begrænsning er, at tilgangen kun er egnet til optimeringsproblemer, men ikke til "rene" genkendelsesproblemer som problemet med tilfredsstillelse af booleske formler , selvom det ofte sker, at metoden er ret anvendelig til at løse optimeringsversioner af de samme problemer, f. for eksempel for det maksimale tilfredsstillelsesproblem booleske formler (Max SAT).

Umuligheden af tilnærmelse har været et frugtbart forskningsfelt inden for beregningskompleksitet lige siden Feige, Goldwasser, Lovasz, Safra og Szegedy i 1990 fastslog, at problemet med at finde det maksimale uafhængige sæt ikke kan tilnærmes . Et år efter Arora beviste PCP-sætningen , har Johnsons tilnærmelsesalgoritmer fra 1974 for det boolske tilfredshedsproblem, sætdækningsproblemet , det uafhængige sætproblem og grafens kromatisk talproblem en optimal tilnærmelsesfaktor (forudsat at P ≠ NP)

Garanteret effektivitet

For nogle tilnærmelsesalgoritmer er det muligt at bevise nogle egenskaber ved tilnærmelsesresultatet. For eksempel er en ρ -approksimationsalgoritme A per definition en algoritme, for hvilken forholdet f ( x ) = værdi/omkostning for at løse tilnærmelsesproblemet A ( x ) for opgave x ikke overstiger (eller ikke mindre, afhængigt af situationen) produktet af koefficienten ρ til den optimale værdi [4] [5] :

{\begin{cases}\mathrm {OPT} \leqslant f(x)\leqslant \rho \mathrm {OPT} ,\rho >1;\\\rho \mathrm {OPT} \leqslant f(x) \leqslant \mathrm {OPT} ,\rho <1.\end{cases}}

Koefficienten ρ kaldes den relative garanterede effektivitet .

En tilnærmelsesalgoritme har en absolut garanteret effektivitet eller en begrænset fejl c , hvis for ethvert problem x ,

(\mathrm {OPT} -c)\leqslant f(x)\leqslant (\mathrm {OPT} +c).

Den garanterede effektivitet , R ( x, y ), af en løsning y for problem x defineres på lignende måde

R(x,y)=\max \left({\frac {\mathrm {OPT} }{f(y)))),{\frac {f(y)}{\mathrm {OPT} } } \right),

hvor f ( y ) er værdi/omkostningsforholdet for løsning y af opgave x . Det er klart, at den garanterede effektivitet ikke er mindre end én og kun er lig med én i det tilfælde, hvor y er den optimale løsning. Hvis algoritme A garanterer en løsning med maksimal effektivitet r ( n ), så siges A at være en r ( n )-approksimationsalgoritme og har en tilnærmelsesfaktor r ( n ) [6] [7] .

Det er let at se, at i tilfælde af minimeringsproblemet giver begge definitioner af garanteret effektivitet samme værdi, mens for maksimeringsproblemet . ${\displaystyle r=\rho ^{-1))$

Det vigtige begreb om relativ fejl forbundet med optimeringsproblemer er defineret i litteraturen på forskellige måder: for eksempel definerer W. Kann [7] det som , og Ausiello et al. [6] som . $|\mathrm {OPT} -f(y)|/\mathrm {OPT}$ ${\displaystyle |\mathrm {OPT} -f(y)|/\max\{\mathrm {OPT} ,f(y)\))$

Den absolutte garanterede effektivitet af en eller anden tilnærmelsesalgoritme A er defineret som $\mathrm {P} _{A}$

\mathrm {P} _{A}=\inf\{r\geqslant 1\mid R_{A}(x)\leqslant r,\forall x\}.

Her betegner x en opgave, og a er den garanterede effektivitet af A for x . $R_{A}(x)$

Således er den øvre grænse for den garanterede effektivitet r for alle mulige opgaver. $\mathrm {P} _{A}$

Den asymptotiske effektivitet defineres på lignende måde : ${\displaystyle R_{A}^{\infty ))$

R_{A}^{\infty }=\inf\{r\geqslant 1\mid \eksisterer n\i \mathbb {Z} ^{+},R_{A}(x)\leqslant r,\ forall x,|x|\geqslant n\}.

Garanteret effektivitet: Nedre (øvre) grænser for minimerings- (maksimering) problemer givet forskellige værdier

	r -ca. [6] [7]	ρ -ca.	vedrører. fejl c [7]	vedrører. c fejl [6]	normer. forhold fejl c [6] [7]	abs. fejl c [6] [7]
max: $f(x)\geqslant$	$r^{-1}\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT} +c\mathrm {VÆRSTE}$	$\mathrm {OPT} -c$
min: $f(x)\leqslant$	$r\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1+c)\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT} +c\mathrm {VÆRSTE}$	$\mathrm {OPT} +c$

Algoritmeudviklingsteknikker

I øjeblikket er der flere standardtilgange til udvikling af en tilnærmelsesalgoritme. Blandt dem:

Grådig algoritme .
Lokal søgning .
Optælling og dynamisk programmering .
Løsning af et svækket konveks programmeringsproblem med mulighed for at opnå en fraktioneret løsning. Opløsningen omdannes derefter til en passende løsning ved afrunding. Populære problemafhjælpningsmetoder er:
1. Reduktion til et lineært programmeringsproblem .
2. Reduktion til problemet med semibestemt programmering .
At definere en simpel metrik for et problem og løse problemet med denne metrik.

Epsilon-medlem

I litteraturen er tilnærmelseskoefficienten for det maksimale (eller minimum) problem skrevet som (eller ) for et eller andet tal i det tilfælde, hvor der er varianter af algoritmen med en tilnærmelseskoefficient for nogen , men ikke for . Et eksempel på en sådan tilnærmelse er uopnåeligheden af koefficienten 7/8 for MAX-3SAT-problemet [8] . $c-\epsilon$ $c+\epsilon$ $c$ $c\mp \epsilon$ $\epsilon >0$ $\epsilon =0$

Noter

↑ MRGarey, RL Graham og JD Ullman. Worst case-analyse af hukommelsesallokeringsalgoritmer. I Proc. Af 4. ACM Symp. Om databehandlingsteori. 143-152, 1972.
↑ D.S. Johnson. Approksimationsalgoritmer til kombinatoriske problemer. J Comput. System Sci. 9, 256-278, 1974.
↑ Gomory, Ralph E. (1958), "Outline of an algorithm for integer solutions to linear programs", Bulletin of the American Mathematical Society 64 (5): 275-279, doi:10.1090/S0002-9904-1958-10224- fire.
↑ Dorit S. Hochbaum, redaktør, Approximation Algorithms for NP-Hard Problems, side XV. PWS Publishing Company
↑ Tjark Vredeveld, eksperimentelle kombinatoriske tilnærmelsesalgoritmer: Guaranteed versus performance, Technische Universiteit Eindhoven, 2002, SBN 90-386-0532-3
↑ 1 2 3 4 5 6 G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela og M. Protasi. Kompleksitet og tilnærmelse: kombinatoriske optimeringsproblemer og deres tilnærmelsesegenskaber . – 1999.
↑ 1 2 3 4 5 6 Viggo Kann. Om tilnærmeligheden af NP-komplette optimeringsproblemer . - 1992.
↑ Johan Hastad. Nogle Optimal Inapproximability Results // Journal of the ACM : journal. – 1999.

Litteratur

Vazirani, Vijay V.Approksimationsalgoritmer . _ - Berlin: Springer, 2003. - ISBN 3-540-65367-8 .
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest og Clifford Stein. Introduktion til algoritmer , anden udgave. MIT Press og McGraw-Hill, 2001. ISBN 0-262-03293-7 . Kapitel 35: Approksimationsalgoritmer, pp. 1022-1056.
Dorit H. Hochbaum, red. Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997. ISBN 0-534-94968-1 . Kapitel 9: Forskellige forestillinger om tilnærmelser: Godt, Bedre, Bedst og mere
Williamson, David & Shmoys, David (26. april 2011), The Design of Approximation Algorithms , Cambridge University Press , ISBN 978-0521195270

Links

Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski og Gerhard Woeginger, A compendium of NP optimization problems

I bibliografiske kataloger	BNF : 16603384f GND : 4500954-5 J9U : 987007475469205171 LCCN : sh2009010988