Tilnærmelsesalgoritme - Approximation algorithm

I datalogi og forskning operationer , approksimationsalgoritmer er effektive algoritmer , der finder omtrentlige løsninger på optimeringsproblemer (især NP-hårde problemer) med beviselige garantier på afstand af den returnerede løsning til den optimale én. Tilnærmelsesalgoritmer opstår naturligvis inden for teoretisk datalogi som en konsekvens af den udbredte P ≠ NP formodning. Under denne formodning kan en bred klasse af optimeringsproblemer ikke løses nøjagtigt i polynomtid . Området tilnærmelsesalgoritmer forsøger derfor at forstå, hvor tæt det er muligt at tilnærme optimale løsninger på sådanne problemer i polynomtid. I et overvældende flertal af tilfældene er garantien for sådanne algoritmer en multiplikativ, udtrykt som et tilnærmelsesforhold eller tilnærmelsesfaktor, dvs. den optimale løsning er altid garanteret inden for en (forudbestemt) multiplikativ faktor for den returnerede løsning. Der er dog også mange tilnærmelsesalgoritmer, der giver en additiv garanti for kvaliteten af ​​den returnerede løsning. Et bemærkelsesværdigt eksempel på en tilnærmelsesalgoritme, der giver begge dele, er den klassiske tilnærmelsesalgoritme for Lenstra , Shmoys og Tardos til planlægning på ikke -relaterede parallelle maskiner .

Design og analyse af tilnærmelsesalgoritmer involverer afgørende et matematisk bevis, der certificerer kvaliteten af ​​de returnerede løsninger i værste fald. Dette adskiller dem fra heuristik såsom annealing eller genetiske algoritmer , der finder rimeligt gode løsninger på nogle input, men ikke giver nogen klar indikation i starten om, hvornår de kan lykkes eller mislykkes.

Der er stor interesse for teoretisk datalogi for bedre at forstå de grænser, vi kan tilnærme visse berømte optimeringsproblemer til. For eksempel er et af de mangeårige åbne spørgsmål inden for datalogi at afgøre, om der er en algoritme, der overgår Christofides 1,5-tilnærmelsesalgoritme til det metriske rejsende sælgerproblem . Ønsket om at forstå hårde optimeringsproblemer ud fra tilnærmelsesperspektivet er motiveret af opdagelsen af ​​overraskende matematiske forbindelser og bredt anvendelige teknikker til at designe algoritmer til hårde optimeringsproblemer. Et velkendt eksempel på førstnævnte er Goemans – Williamson-algoritmen til maksimal snit , som løser et grafteoretisk problem ved hjælp af højdimensionel geometri.

Introduktion

Et simpelt eksempel på en tilnærmelsesalgoritme er en for det minimale toppunktdækningsproblem , hvor målet er at vælge det mindste sæt hjørner, så hver kant i inputgrafen indeholder mindst et valgt toppunkt. En måde at finde et toppunktdæksel på er at gentage følgende proces: Find en afdækket kant, tilføj begge dens endepunkter til dækslet, og fjern alle kanter, der indfalder til begge toppunkter fra grafen. Da ethvert toppunktdæksel i inputgrafen skal bruge et særskilt toppunkt til at dække hver kant, der blev overvejet i processen (da det danner en matchning ), er det producerede vertex -dækning derfor højst dobbelt så stort som det optimale. Med andre ord er dette en tilnærmelsesfaktor tilnærmelsesalgoritme med en tilnærmelsesfaktor på 2. Under de seneste unikke spilformodninger er denne faktor endda den bedst mulige.

NP-hårde problemer varierer meget i deres tilnærmelse; nogle, såsom rygsækproblemet , kan tilnærmes inden for en multiplikativ faktor for enhver fast , og derfor producere løsninger vilkårligt tæt på det optimale (en sådan familie af tilnærmelsesalgoritmer kaldes et polynomisk tidsnærmetingsskema eller PTAS). Andre er umulige at tilnærme inden for en konstant eller endda polynom faktor, medmindre P = NP , som i tilfælde af det maksimale klikproblem . Derfor er en vigtig fordel ved at studere tilnærmelsesalgoritmer en finkornet klassifikation af vanskeligheden ved forskellige NP-hårde problemer ud over den, som teorien om NP-fuldstændighed giver . Med andre ord, selvom NP-komplette problemer kan være ækvivalente (under polynomiske tidsreduktioner) til hinanden fra perspektivet af nøjagtige løsninger, opfører de tilsvarende optimeringsproblemer sig meget forskelligt fra perspektivet af omtrentlige løsninger. ${\ displaystyle 1+ \ epsilon}$${\ displaystyle \ epsilon> 0}$

Algoritme design teknikker

På nuværende tidspunkt er der flere etablerede teknikker til at designe tilnærmelsesalgoritmer. Disse omfatter følgende.

1. Grådig algoritme
2. Lokal søgning
3. Optælling og dynamisk programmering
4. Løsning af en konveks programmeringsrelaksation for at få en fraktioneret løsning. Derefter konverteres denne fraktionsopløsning til en gennemførlig løsning ved en passende afrunding. De populære afslapninger omfatter følgende.
   • Lineær programmering lempelserne
   • Semidefinite programmering afslapninger
5. Primal-dual metoder
6. Dobbelt montering
7. Indlejring af problemet i en metric og derefter løse problemet på metricen. Dette er også kendt som metrisk indlejring.
8. Tilfældig prøveudtagning og brug af tilfældighed generelt i forbindelse med ovenstående metoder.

Efterfølgende garantier

Selvom tilnærmelsesalgoritmer altid giver en a priori worst case -garanti (det være sig additiv eller multiplikativ), giver de i nogle tilfælde også en a posteriori -garanti, der ofte er meget bedre. Dette er ofte tilfældet for algoritmer, der fungerer ved at løse en konveks lempelse af optimeringsproblemet på det givne input. For eksempel er der en anden tilnærmelsesalgoritme til minimum vertex -dækning, der løser en lineær programmeringsrelaksation for at finde et vertex -dækning, der højst er dobbelt så meget som afslapningens værdi. Da værdien af ​​afslapningen aldrig er større end størrelsen på det optimale toppunktdæksel, giver dette endnu en 2-tilnærmelsesalgoritme. Selvom dette svarer til a priori -garantien for den tidligere tilnærmelsesalgoritme, kan sidstnævnte garanti være meget bedre (når værdien af ​​LP -afslapning langt fra størrelsen af ​​det optimale toppunktdæksel).

Tilnærmelseens hårdhed

Tilnærmelsesalgoritmer som forskningsområde er nært beslægtet med og informeret af utilnærmelighedsteori, hvor ikke-eksistensen af ​​effektive algoritmer med visse tilnærmelsesforhold bevises (betinget af udbredte troede hypoteser såsom P ≠ NP-formodningen) ved hjælp af reduktioner . I tilfælde af det metriske rejsende sælgerproblem udelukker det bedst kendte utilnærmelsesresultat algoritmer med et tilnærmelsesforhold mindre end 123/122 ≈ 1.008196, medmindre P = NP, Karpinski, Lampis, Schmied. Sammen med kendskabet til eksistensen af ​​Christofides '1,5 tilnærmelsesalgoritme, fortæller dette os, at tærsklen for tilnærmelse til metrisk rejsende sælger (hvis den findes) er et sted mellem 123/122 og 1,5.

Selvom der er påvist utilstrækkelige resultater siden 1970'erne, blev sådanne resultater opnået ad hoc -midler, og der var ikke tilgængelig systematisk forståelse på det tidspunkt. Det er først siden 1990 -resultatet af Feige, Goldwasser, Lovász, Safra og Szegedy om uafhængighed af Independent Set og den berømte PCP -sætning, at moderne værktøjer til at bevise utilnærmelsesresultater blev afdækket. PCP -sætningen viser for eksempel, at Johnsons tilnærmelsesalgoritmer fra 1974 for Max SAT , sætdæksel , uafhængigt sæt og farvning alle opnår det optimale tilnærmelsesforhold, forudsat at P ≠ NP.

Praktisk

Ikke alle tilnærmelsesalgoritmer er egnede til direkte praktiske applikationer. Nogle involverer løsning af ikke-triviel lineær programmering / semidefinite afslapninger (som selv kan påberåbe sig ellipsoide algoritmen ), komplekse datastrukturer eller sofistikerede algoritmiske teknikker, hvilket fører til vanskelige implementeringsproblemer eller forbedret driftstid (over eksakte algoritmer) kun på upraktisk store input . Implementerings- og driftstidsspørgsmål til side, garantierne fra tilnærmelsesalgoritmer er måske ikke selv stærke nok til at begrunde deres overvejelse i praksis. På trods af deres manglende evne til at blive brugt "out of the box" i praktiske applikationer, kan ideerne og indsigterne bag designet af sådanne algoritmer ofte inkorporeres på andre måder i praktiske algoritmer. På denne måde er undersøgelsen af ​​selv meget dyre algoritmer ikke en helt teoretisk forfølgelse, da de kan give værdifuld indsigt.

I andre tilfælde, selvom de første resultater er af rent teoretisk interesse, med tiden med en forbedret forståelse, kan algoritmerne blive forfinet til at blive mere praktiske. Et sådant eksempel er den oprindelige PTAS for euklidisk TSP af Sanjeev Arora (og uafhængigt af Joseph Mitchell ), som havde en uoverkommelig driftstid på til en tilnærmelse. Men inden for et år blev disse ideer inkorporeret i en nær-lineær tidsalgoritme for enhver konstant . ${\ displaystyle n^{O (1/\ epsilon)}}$${\ displaystyle 1+ \ epsilon}$${\ displaystyle O (n \ log n)}$${\ displaystyle \ epsilon> 0}$

Ydelsesgarantier

For nogle tilnærmelsesalgoritmer er det muligt at bevise visse egenskaber ved tilnærmelse af det optimale resultat. For eksempel er en ρ -approximeringsalgoritme A defineret til at være en algoritme, for hvilken det er bevist, at værdien/omkostningen, f ( x ), af den omtrentlige løsning A ( x ) til en forekomst x ikke vil være mere (eller mindre, afhængigt af situationen) end en faktor ρ gange værdien, OPT, for en optimal løsning.

${\ displaystyle {\ begin {cases} \ mathrm {OPT} \ leq f (x) \ leq \ rho \ mathrm {OPT}, \ qquad {\ mbox {if}} \ rho> 1; \\\ rho \ mathrm {OPT} \ leq f (x) \ leq \ mathrm {OPT}, \ qquad {\ mbox {if}} \ rho <1. \ end {cases}}}$

Faktoren ρ kaldes den relative ydelsesgaranti . En tilnærmelsesalgoritme har en absolut ydelsesgaranti eller begrænset fejl c , hvis det er blevet bevist for hver forekomst x det

${\ displaystyle (\ mathrm {OPT} -c) \ leq f (x) \ leq (\ mathrm {OPT} +c).}$

På samme måde defineres ydelsesgarantien , R ( x, y ), for en løsning y til en forekomst x som

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

hvor f ( y ) er værdien/prisen på løsningen y for eksempel x . Det er klart, at ydelsesgarantien er større end eller lig med 1 og lig med 1, hvis og kun hvis y er en optimal løsning. Hvis en algoritme A garantier for at returnere opløsninger med en sikkerhed på højst r ( n ), derefter A siges at være en r ( n ) -approximation algoritme og har en tilnærmelse forholdet af r ( n ). På samme måde siges et problem med en r ( n ) -approximeringsalgoritme at være r ( n ) - tilnærmeligt eller har et tilnærmelsesforhold på r ( n ).

Ved minimeringsproblemer giver de to forskellige garantier det samme resultat, og at for maksimeringsproblemer svarer en relativ ydelsesgaranti på ρ til en ydelsesgaranti på . I litteraturen er begge definitioner almindelige, men det er klart, hvilken definition der bruges, da der for maksimeringsproblemer er ρ ≤ 1, mens r ≥ 1. ${\ displaystyle r = \ rho ^{-1}}$

Den absolutte ydelsesgaranti for en eller anden tilnærmelsesalgoritme A , hvor x refererer til en forekomst af et problem, og hvor er ydelsesgarantien for A på x (dvs. ρ for problemforekomst x ) er: ${\ displaystyle \ mathrm {P} _ {A}}$${\ displaystyle R_ {A} (x)}$

${\ displaystyle \ mathrm {P} _ {A} = \ inf \ {r \ geq 1 \ mid R_ {A} (x) \ leq r, \ forall x \}.}$

Det vil sige, at det er den største grænse for tilnærmelsesforholdet, r , som man ser over alle mulige tilfælde af problemet. På samme måde er det asymptotiske ydelsesforhold : ${\ displaystyle \ mathrm {P} _ {A}}$ ${\ displaystyle R_ {A}^{\ infty}}$

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

Det vil sige, at det er det samme som det absolutte ydelsesforhold med en lavere grænse n for størrelsen af ​​problemforekomster. Disse to typer nøgletal bruges, fordi der findes algoritmer, hvor forskellen mellem disse to er signifikant.

Ydelsesgarantier

	r -ca.	ρ -ca.	rel. fejl	rel. fejl	norm. rel. fejl	abs. fejl
max: ${\ displaystyle f (x) \ geq}$	${\ displaystyle r^{-1} \ mathrm {OPT}}$	${\ displaystyle \ rho \ mathrm {OPT}}$	${\ displaystyle (1-c) \ mathrm {OPT}}$	${\ displaystyle (1-c) \ mathrm {OPT}}$	${\ displaystyle (1-c) \ mathrm {OPT} +c \ mathrm {WORST}}$	${\ displaystyle \ mathrm {OPT} -c}$
min: ${\ displaystyle f (x) \ leq}$	${\ displaystyle r \ mathrm {OPT}}$	${\ displaystyle \ rho \ mathrm {OPT}}$	${\ displaystyle (1+c) \ mathrm {OPT}}$	${\ displaystyle (1-c)^{-1} \ mathrm {OPT}}$	${\ displaystyle (1-c)^{-1} \ mathrm {OPT} +c \ mathrm {WORST}}$	${\ displaystyle \ mathrm {OPT} +c}$

Epsilon -vilkår

I litteraturen betyder et tilnærmelsesforhold for et problem med maksimering (minimering) af c - ϵ (min: c + ϵ), at algoritmen har et tilnærmelsesforhold på c ∓ ϵ for vilkårlig ϵ> 0, men at forholdet ikke har (eller kan ikke) vises for ϵ = 0. Et eksempel på dette er den optimale utilnærmelse-inexistens af tilnærmelse-forholdet 7 /8 + ϵ for tilfredsstillende MAX-3SAT- forekomster på grund af Johan Håstad . Som nævnt tidligere siges problemet at når c = 1 har et tilnærmelsesskema for polynom-tid .

Et ϵ-udtryk kan forekomme, når en tilnærmelsesalgoritme introducerer en multiplikativ fejl og en konstant fejl, mens minimumsoptimum for forekomster af størrelse n går til uendelig som n gør. I dette tilfælde er tilnærmelsesforholdet c ∓ k / OPT = c ∓ o (1) for nogle konstanter c og k . I betragtning af arbitrær ε> 0, kan man vælge en tilstrækkelig stor N sådan at udtrykket k / OPT <ε for alle n ≥ N . For hvert fast ϵ kan forekomster af størrelse n <N løses ved brutal kraft og derved vise et tilnærmelsesforhold - eksistens af tilnærmelsesalgoritmer med en garanti - på c ∓ ϵ for hver ϵ> 0.

Se også

• Dominansanalyse overvejer garantier med hensyn til rangen af ​​den beregnede løsning.
• PTAS - en type tilnærmelsesalgoritme, der tager tilnærmelsesforholdet som en parameter
• APX er klassen af ​​problemer med en tilnærmelsesalgoritme med konstant faktor
• Tilnærmelse bevarer reduktion
• Den nøjagtige algoritme

Citater

Referencer

• Vazirani, Vijay V. (2003). Tilnærmelsesalgoritmer . Berlin: Springer. ISBN 978-3-540-65367-7.
• 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: Approximation Algorithms, s. 1022–1056.
• Dorit S. 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 P .; Shmoys, David B. (26. april 2011), Design of Approximation Algorithms , Cambridge University Press , ISBN 978-0521195270

eksterne links

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski og Gerhard Woeginger , Et kompendium af NP -optimeringsproblemer .