Algoritmo di approssimazione: differenze tra le versioni

Versione delle 22:46, 22 mar 2014

Versione delle 23:44, 22 mar 2014

Riga 1:

{{T|inglese|informatica|marzo 2014}}

Nell'[[informatica]] e nella [[ricerca operativa]], un '''algoritmo di approssimazione''' è un [[algoritmo]] usato per trovare soluzioni approssimate a [[Problema di ottimizzazione|problemi di ottimizzazione]]. Gli algoritmi di approssimazione sono spesso associati a problemi [[NP-difficile|NP-difficili]]; poiché è improbabile che ci possano essere algoritmi esatti efficienti in [[tempo polinomiale]] che risolvono problemi NP-difficili, ci si accontenta di soluzioni subottimali in tempo polinomiale. Diversamente dall'[[euristica]], che di solito trova soluzioni ragionevolmente buone in tempi ragionevolmente veloci, in questo caso si vogliono soluzioni di qualità dimostrabile e tempi di esecuzione con limiti dimostrabili. Idealmente, l'approssimazione è ottimale fino a un piccolo fattore costante (ad esempio entro il 5% della soluzione ottimale). Gli algoritmi di approssimazione sono usati sempre di pù per problemi dove gli algoritmi esatti in tempo polinomiale sono noti ma risultano troppo costosi a causa della dimensione dell'input.

Un esempio tipico di un algoritmo di approssimazione è quello per la [[Problema della copertura dei vertici|copertura dei vertici]] nei [[Grafo|grafi]]: trovare uno spigolo scoperto e aggiungere "entrambi" gli estremi alla copertura dei vertici, finché non rimane nessuno. È chiaro che la copertura risultante è al massimo due volte più grande di quella ottimale. Questo è un [[algoritmo di approssimazione a fattore costante]] con un fattore di 2.

Riga 14:

L'inapprossimabilità è stata un'area di ricerca fruttuosa nel campo della teoria della complessità computazionale fin dal risultato del 1990 di Feige, Goldwasser, Lovasz, Safra e Szegedy sull'inapprossimabilità dell'[[Insieme indipendente (teoria dei grafi)|insieme indipendente]]. Dopo che Arora et al. dimostrarono il [[teorema PCP]] un anno dopo, si è ormai mostrato che gli algoritmi di approssimazione del 1974 di Johnson per il Max SAT, la copertura degli insiemi, l'insieme indipendente e la colorazione raggiungono tutti il rapporto ottimale di approssimazione, assumendo P != NP.

<!--

==Garanzie di prestazione ==

== Performance guarantees ==

ForPer somealcuni approximationalgoritmi algorithmsdi itapprossimazione isè possiblepossibile toprovare provecerte certainproprietà propertiessull'approssimazione aboutdel therisultato approximation of the optimum resultottimale. ForPer exampleesempio, aun '''algoritmo di approssimazione ''ρ''-approximation algorithm''' ''A'' issi defineddefinisce tocome beun analgoritmo algorithmper foril whichquale itsi beenè provenprovato thatche theil valuevalore/costcosto, ''f''(''x''), ofdella thesoluzione approximate solutionapprossimata ''A''(''x'') toper an instanceun'istanza ''x'' willnon notsarà be morepiù (oro lessmeno, dependingsecondo onla the situationsituazione) thangrande adi factorun fattore ''ρ'' timesvolte rispetto theal valuevalore, OPT, ofdi anuna optimumsoluzione solutionottima.

:<math>\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}</math>

TheIl factorfattore ''ρ'' isè called thechiamato ''relativegaranzia performancedi guaranteeprestazione relativa''. AnUn approximationalgoritmo algorithmdi hasapprossimazione anha una ''absolutegaranzia performancedi guaranteeprestazione assoluta'' oro ''boundederrore errorlimitato'' ''c'', if itse hasè beenstato provenprovato forper everyogni instanceistanza ''x'' thatche

:<math> (\mathrm{OPT} - c) \leq f(x) \leq (\mathrm{OPT} + c).</math>

SimilarlySimilmente, thela ''performancegaranzia guaranteedi prestazione'', ''R''(''x,y''), ofdi auna solutionsoluzione ''y'' toper an instanceun'istanza ''x'' isè defineddefinita ascome

:R(x,y) = <math> \max \left ( \frac{OPT}{f(y)}, \frac{f(y)}{OPT} \right ),</math>

wheredove ''f''(''y'') isè theil valuevalore/costcosto ofdella the solutionsoluzione ''y'' forper the instancel'istanza ''x''. ClearlyChiaramente, thela performancegaranzia guaranteedi isprestazione greaterè thanmaggiore ordi equalo touguale 1 and equal toa 1 ifse ande onlysolo ifse ''y'' isè anuna optimalsoluzione solutionottima. IfSe anun algorithmalgoritmo ''A'' guaranteesgarantisce todi returnrestituire solutionssoluzioni withcon auna performancegaranzia guaranteedi ofprestazione atal mostmassimo di ''r''(''n''), thenallora si dice che ''A'' isè saidun toalgoritmo bedi anapprossimazione ''r''(''n'')-approximation algorithme andha has anun ''approximationrapporto ratiodi approssimazione'' ofdi ''r''(''n''). LikewiseSimilmente, aun problemproblema withcon anun algoritmo di approssimazione ''r''(''n'')-approximation algorithm issi saiddice toche beè r''(''n'')''-''approximableapprossimabile'' oro haveche anha approximationun ratiorapporto ofdi approssimazione di ''r''(''n'').<ref name=ausiello99complexity>{{citecita booklibro|titletitolo=Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties|yearanno=1999|authorautore=G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, ande M. Protasi}}</ref><ref name="kann92onthe">{{citecita booklibro|titletitolo=On the Approximability of NP-complete Optimization Problems|authorautore=Viggo Kann|yearanno=1992|url=http://www.csc.kth.se/~viggo/papers/phdthesis.pdf}}</ref>

OneSi maypuò notenotare thatche, per i forproblemi minimizationdi problemsminimizzazione, thele twodue differentdiverse guaranteesgaranzie provideforniscono thelo samestesso resultrisultato ande thatche, per i forproblemi maximizationdi problemsmassimizzazione, auna garanzia relativedi performanceprestazione guaranteerelativa ofdi ρ isè equivalent toequivalente a performanceuna garanzia di guaranteeprestazione ofdi <math>r = \rho^{-1}</math>. InNella the literatureletteratura, bothentrambe definitionsle aredefinizioni commonsono butcomuni itma isè clearchiaro whichqual definitionè isla useddefinizione sinceusata da allora, forper maximizationi problemsproblemi di massimizzazione, asin quanto ρ ≤ 1 whilementre r ≥ 1.

TheLa ''absolutegaranzia performancedi guaranteeprestazione assoluta'' <math>\Rho_A</math> ofdi someun approximationqualche algorithmalgoritmo di approssimazione ''A'', wheredove ''x'' referssi toriferisce an instanceall'istanza ofdi aun problemproblema, ande wheredove <math>R_A(x)</math> isè thela performancegaranzia guaranteedi ofprestazione di ''A'' onsu ''x'' (i.e.cioè ρ forper l'istanza problemdel instanceproblema ''x'') isè:

:<math> \Rho_A = \inf \{ r \geq 1 \mid R_A(x) \leq r, \forall x \}.</math>

ThatQuesto isvuol todire say thatche <math>\Rho_A</math> isè theil largestlimite boundpiù ongrande thesul approximationrapporto ratiodi approssimazione, ''r'', thatche onesi seesvede oversu alltutte possiblele instancespossibili ofistanze thedel problemproblema. LikewiseSimilmente, theil ''asymptoticrapporto di performanceprestazione ratioasintotica'' <math>R_A^\infty</math> isè:

:<math> R_A^\infty = \inf \{ r \geq 1 \mid \exists n \in \mathbb{Z}^+, R_A(x) \leq r, \forall x, |x| \geq n\}. </math>

Questo vuol dire che è lo stesso del ''rapporto di prestazione assoluta'', con un limite inferiore ''n'' sulla dimensione delle istanze del problema. Questi due tipi di rapporti si usano perché esistono algoritmi dove la differenza tra i due è significativa.

That is to say that it is the same as the ''absolute performance ratio'', with a lower bound ''n'' on the size of problem instances. These two types of ratios are used because there exist algorithms where the difference between these two is significant.

{| class="wikitable"

|+Garanzie di prestazione

|+Performance guarantees

|-

! !! ''r''-approxappross.<ref name="ausiello99complexity"/><ref name="kann92onthe"/> !! ''ρ''-approxappross. !! errore rel. error<ref name="kann92onthe"/> !! errore rel. error<ref name="ausiello99complexity"/> !! norm.errore rel. errornorm.<ref name="ausiello99complexity"/><ref name="kann92onthe"/> !! abs.errore errorass.<ref name="ausiello99complexity"/><ref name="kann92onthe"/>

|-

! max: <math>f(x) \geq</math>

Riga 54:

|-

|}

<!--

==Algorithm design techniques==

By now there are several standard techniques that one tries to design an approximation algorithm. These include the following ones.