Algoritmo di approssimazione: differenze tra le versioni

Versione delle 21:50, 22 mar 2014

Versione attuale delle 16:58, 2 feb 2025

(18 versioni intermedie di 8 utenti non mostrate)

Riga 1:

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ùpiù per problemi dove gli algoritmi esatti in tempo polinomiale sono noti ma risultano troppo costosi a causa della dimensione dell'input.

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

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 ne 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.

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.

I problemi NP-difficili variano grandemente nella loro approssimabilità; alcuni, come il [[problema dell'impacchettamento]], può essere approssimato entro un qualsiasi fattore maggiore di 1 (tale famiglia di algoritmi di approssimazione è chiamata spesso [[schema di approssimazione in tempo polinomiale]] o ''PTAS''). Altri sono impossibili da approssimare entro qualsiasi costante, o perfino fattore polinomiale, a meno che [[Classi di complessità P e NP|P = NP]], come il [[problema della massima cricca]].

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.

I problemi NP-difficili variano grandemente nella loro approssimabilità; alcuni, come il [[problema dell'impacchettamento]], può essere approssimato entro un qualsiasi fattore maggiore di 1 (tale famiglia di algoritmi di approssimazione è chiamata spesso [[schema di approssimazione in tempo polinomiale]] o ''PTAS''). Altri sono impossibili da approssimare entro qualsiasi costante, o perfino fattore polinomiale a meno che [[Classi di complessità P e NP|P = NP]], come il [[problema della massima cricca]].

I problemi NP-difficili spesso possono essere espressi come [[Programmazione lineare|programmi interi]] (''integer programs'', IP) e risolti esattamente in [[tempo esponenziale]]. Molti algoritmi di approssimazione emergono dal [[rilassamento della programmazione lineare]] del programma intero.

<!--

Not all approximation algorithms are suitable for all practical applications. They often use IP/LP/[[semidefinite programming|Semidefinite]] solvers, complex data structures or sophisticated algorithmic techniques which lead to difficult implementation problems. Also, some approximation algorithms have impractical running times even though they are polynomial time, for example O(''n''²⁰⁰⁰). Yet the study of even very expensive algorithms is not a completely theoretical pursuit as they can yield valuable insights. A classic example is the initial PTAS for [[Euclidean traveling salesman problem|Euclidean TSP]] due to [[Sanjeev Arora]] which had prohibitive running time, yet within a year, Arora refined the ideas into a linear time algorithm. Such algorithms are also worthwhile in some applications where the running times and cost can be justified e.g. [[computational biology]], [[financial engineering]], [[transportation planning]], and [[inventory management]]. In such scenarios, they must compete with the corresponding direct IP formulations.

Non tutti gli algoritmi di approssimazione sono adatti per tutte le applicazioni pratiche. Spesso usano risolutori IP/LP/[[Programmazione semidefinita|semidefiniti]], [[Struttura dati|strutture dati]] complesse o tecniche algoritmiche sofisticate che conducono a problemi di difficile implementazione. Inoltre, alcuni algoritmi di approssimazione hanno tempi di esecuzione poco pratici anche se sono in tempo polinomiale, ad esempio O(''n''²⁰⁰⁰). Tuttavia lo studio di algoritmi anche molto costosi non è una ricerca completamente teorica, in quanto possono fornire preziose intuizioni. Un esempio classico è il PTAS iniziale per il [[Problema del commesso viaggiatore#TSP euclideo|TSP euclideo]] dovuto a [[Sanjeev Arora]] che aveva un tempo di esecuzione proibitivo; tuttavia entro un anno, Arora perfezionò le idee in un algoritmo in tempo lineare. Tali algoritmi sono validi anche in alcune applicazioni dove i tempi e il costo di esecuzione possono essere giustificati, ad es. [[biologia computazionale]], [[ingegneria finanziaria]], [[Trasporto|pianificazione dei trasporti]] e [[Inventario|gestione degli inventari]]. In tali scenari, essi devono competere con le corrispondenti formulazioni IP dirette.

Another limitation of the approach is that it applies only to optimization problems and not to "pure" [[decision problem]]s like [[boolean satisfiability problem|satisfiability]], although it is often possible to conceive optimization versions of such problems, such as the [[maximum satisfiability problem]] (Max SAT).

Un'altra limitazione dell'approccio è che esso si applica soltanto ai problemi di ottimizzazione e non ai [[Problema decisionale|problemi di decisione]] "puri" come la [[Soddisfacibilità booleana|soddisfacibilità]], sebbene sia spesso possibile concepire versionsi di ottimizzazione di tali problemi, come il [[problema della massima soddisfacibilità]] (Max SAT).

Inapproximability has been a fruitful area of research in computational complexity theory since the 1990 result of Feige, Goldwasser, Lovasz, Safra and Szegedy on the inapproximability of [[Independent set (graph theory)|Independent Set]]. After Arora et al. proved the [[PCP theorem]] a year later, it has now been shown that Johnson's 1974 approximation algorithms for Max SAT, Set Cover, Independent Set and Coloring all achieve the optimal approximation ratio, assuming P != NP.

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 è mostrato che gli algoritmi di approssimazione elaborati nel 1974 da 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.

== Performance guarantees ==

For some approximation algorithms it is possible to prove certain properties about the approximation of the optimum result. For example, a '''''ρ''-approximation algorithm''' ''A'' is defined to be an algorithm for which it been proven that the value/cost, ''f''(''x''), of the approximate solution ''A''(''x'') to an instance ''x'' will not be more (or less, depending on the situation) than a factor ''ρ'' times the value, OPT, of an optimum solution.

==Garanzie di prestazione ==

Per alcuni algoritmi di approssimazione è possibile provare certe proprietà sull'approssimazione del risultato ottimale. Per esempio, un '''algoritmo di approssimazione ''ρ''''' ''A'' si definisce come un algoritmo per il quale si è provato che il valore/costo, ''f''(''x''), della soluzione approssimata ''A''(''x'') per un'istanza ''x'' non sarà più (o meno, secondo la situazione) grande di un fattore ''ρ'' volte rispetto al valore, OPT, di una soluzione ottima.

:<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 algorithmsi isdice saidche to 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 since,usata forda maximizationallora problemsper i problemi 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 55 ⟶ 53:

|}

==Tecniche di progettazione degli algoritmi==

==Algorithm design techniques==

Ormai ci sono parecchie tecniche standard che si usano per progettare un algoritmo di approssimazione. Queste comprendono le seguenti.

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

# [[GreedyAlgoritmo algorithmgreedy]]

# [[Ricerca locale]]

# [[Local search (optimization)|Local search]]

# Enumerazione e [[programmazione dinamica]]

# Enumeration and [[dynamic programming]]

# Risolvere un rilassamento della [[programmazione convessa]] per ottenere una soluzione frazionaria. Poi convertire questa soluzione frazionaria in una soluzione fattibile mediante qualche arrotondamento appropriato. I rilassamenti più conosciuti includono i seguenti.

# Solving a [[convex programming]] relaxation to get a fractional solution. Then converting this fractional solution into a feasible solution by some appropriate rounding. The popular relaxations include the following.

## Rilassamento della [[programmazione lineare]]

## [[Linear programming]] relaxation

## Rilassamento della [[programmazione semidefinita]]

## [[Semidefinite programming]] relaxation

# Incorporare il problema in qualche metrica semplice e poi risolverlo sulla metrica. Questa è conosciuta anche come incoporazione metrica.

# Embedding the problem in some simple metric and then solving the problem on the metric. This is also known as metric embedding.

== Termini epsilon ==

Nella letteratura, un rapporto di approssimazione per un problema di massimizzazione (minimizzazione) di ''c'' - ϵ (min: ''c'' + ϵ) significa che l'algoritmo ha un rapporto di approssimazione di ''c'' ∓ ϵ per un arbitrario ϵ > 0 ma che il rapporto non si mostra (o non si può mostrare) per ϵ = 0. Un esempio di questo è il rapporto ottimale di inapprossimabilità — inesistenza dell'approssimabilità — di 7 / 8 + ϵ per le istanze soddisfacibili di [[MAX-3SAT]] dovuto a [[Johan Håstad]].<ref name="hastad99someoptimal">{{cita pubblicazione|titolo=Some Optimal Inapproximability Results|rivista=Journal of the ACM|anno=1999|url=http://www.nada.kth.se/~johanh/optimalinap.ps|autore=[[Johan Håstad]]}}</ref> Come menzionato in precedenza, quando ''c'' = 1, si dice che il problema ha uno [[schema di approssimazione in tempo polinomiale]].

Un termine ϵ può apparire quando un algoritmo di approssimazione introduce un errore moltiplicativo e un errore costante mentre l'ottimo minimo delle istanze di dimensione ''n'' va a infinito quando lo fa ''n''. In questo caso, il rapporto di approssimazione è ''c'' ∓ ''k'' / OPT = ''c'' ∓ o(1) per alcune costanti ''c'' e ''k''. Dato un arbitrario ϵ > 0, si può scegliere un ''N'' grande abbastanza tale che il termine ''k'' / OPT < ϵ per ogni ''n ≥ N''. Per ogni ϵ fisso, le istanze di dimensione ''n < N'' possono essere risolte mediante la [[Metodo forza bruta|forza bruta]], mostrando in tal modo un rapporto di approssimazione — esistenza di algoritmi di approssimazione con una garanzia — di ''c'' ∓ ϵ per ogni ϵ > 0.

== Epsilon terms ==

In the literature, an approximation ratio for a maximization (minimization) problem of ''c'' - ϵ (min: ''c'' + ϵ) means that the algorithm has an approximation ratio of ''c'' ∓ ϵ for arbitrary ϵ > 0 but that the ratio has not (or cannot) be shown for ϵ = 0. An example of this is the optimal inapproximability — inexistence of approximation — ratio of 7 / 8 + ϵ for satisfiable [[MAX-3SAT]] instances due to [[Johan Håstad]].<ref name="hastad99someoptimal">{{cite journal|title=Some Optimal Inapproximability Results|journal=Journal of the ACM|year=1999|url=http://www.nada.kth.se/~johanh/optimalinap.ps|author=[[Johan Håstad]]}}</ref> As mentioned previously, when ''c'' = 1, the problem is said to have a [[polynomial-time approximation scheme]].

An ϵ-term may appear when an approximation algorithm introduces a multiplicative error and a constant error while the minimum optimum of instances of size ''n'' goes to infinity as ''n'' does. In this case, the approximation ratio is ''c'' ∓ ''k'' / OPT = ''c'' ∓ o(1) for some constants ''c'' and ''k''. Given arbitrary ϵ > 0, one can choose a large enough ''N'' such that the term ''k'' / OPT < ϵ for every ''n ≥ N''. For every fixed ϵ, instances of size ''n < N'' can be solved by brute force , thereby showing an approximation ratio — existence of approximation algorithms with a guarantee — of ''c'' ∓ ϵ for every ϵ > 0.

-->

==Note==

<references/>

==Bibliografia==

* {{cita libro book

| cognome = Vazirani

| nome = Vijay V.

Riga 83 ⟶ 81:

| città = Berlin

| isbn = 3-540-65367-8 }}

* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], e [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', 2ª edizione. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Capitolo 35: "Approximation Algorithm"s, pp.&nbsp;1022&ndash;10561022–1056.

* [[Dorit H. Hochbaum]] (cur.), ''[[Approximation Algorithms for NP-Hard problems]]'', PWS Publishing Company, 1997. ISBN 0-534-94968-1. Capitolo 9: "Various Notions of Approximations: Good, Better, Best, and More".

* {{cita testo|cognome1=Williamson|nome1=David P.|cognome2=Shmoys|nome2=David B.|wkautore2=David Shmoys|data=26 aprile 2011|titolo=The Design of Approximation Algorithms|città=|editore=[[Cambridge University Press]]|isbn=978-05211952700-521-19527-0}}

==Collegamenti esterni==

* {{FOLDOC|approximation algorithm|approximation algorithm}}

* Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, [[Marek Karpinski]] e Gerhard Woeginger, [http://www.nada.kth.se/~viggo/wwwcompendium/ ''A compendium of NP optimization problems''].

{{Controllo di autorità}}

{{Portali|Matematica|Informatica}}

{{Portale|Informatica|Matematica}}

[[Categoria:Algoritmi|Approssimazione]]

[[Categoria:ComplessitàTeoria della complessità computazionale]]

[[Categoria:Matematica per l'informatica]]