Algoritmo di approssimazione: differenze tra le versioni

Versione delle 23:44, 22 mar 2014

Versione attuale delle 16:58, 2 feb 2025

(14 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.

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

Riga 9 ⟶ 7:

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.

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 difficili problemi di implememtazionedifficile 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 appicazioniapplicazioni 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.

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

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 delelaborati nel 1974 dida 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 ==

Riga 28 ⟶ 26:

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

dove ''f''(''y'') è il valore/costo della soluzione ''y'' per l'istanza ''x''. Chiaramente, la garanzia di prestazione è maggiore di o uguale a 1 se e solo se ''y'' è una soluzione ottima. Se un algoritmo ''A'' garantisce di restituire soluzioni con una garanzia di prestazione al massimo di ''r''(''n''), allora si dice che ''A'' è un algoritmo di approssimazione ''r''(''n'') e ha un ''rapporto di approssimazione'' di ''r''(''n''). Similmente, un problema con un algoritmo di approssimazione ''r''(''n'') si dice che è ''r''(''n'')''-''approssimabile'' o che ha un rapporto di approssimazione di ''r''(''n'').<ref name=ausiello99complexity>{{cita libro|titolo=Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties|anno=1999|autore=G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela e M. Protasi}}</ref><ref name="kann92onthe">{{cita libro|titolo=On the Approximability of NP-complete Optimization Problems|autore=Viggo Kann|anno=1992|url=http://www.csc.kth.se/~viggo/papers/phdthesis.pdf}}</ref>

Si può notare che, per i problemi di minimizzazione, le due diverse garanzie forniscono lo stesso risultato e che, per i problemi di massimizzazione, una garanzia di prestazione relativa di ρ è equivalente a una garanzia di prestazione di <math>r = \rho^{-1}</math>. Nella letteratura, entrambe le definizioni sono comuni ma è chiaro qual è la definizione usata da allora, per i problemi di massimizzazione, in quanto ρ ≤ 1 mentre r ≥ 1.

La ''garanzia di prestazione assoluta'' <math>\Rho_A</math> di un qualche algoritmo di approssimazione ''A'', dove ''x'' si riferisce all'istanza di un problema, e dove <math>R_A(x)</math> è la garanzia di prestazione di ''A'' su ''x'' (cioè ρ per l'istanza del problema ''x'') è:

Riga 54 ⟶ 52:

|-

|}

<!--

==Algorithm design techniques==

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

# [[Greedy algorithm]]

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

# Enumeration and [[dynamic programming]]

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

## [[Linear programming]] relaxation

## [[Semidefinite programming]] relaxation

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

==Tecniche di progettazione degli algoritmi==

== Epsilon terms ==

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

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

# [[Algoritmo greedy]]

# [[Ricerca locale]]

# Enumerazione e [[programmazione dinamica]]

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

## Rilassamento della [[programmazione lineare]]

## Rilassamento della [[programmazione semidefinita]]

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

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

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==

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]]