Algoritmo di approssimazione: differenze tra le versioni

Versione delle 00:39, 23 mar 2014

Versione delle 00:49, 23 mar 2014

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.

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.

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

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:

==Tecniche di progettazione degli algoritmi==

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

# [[Algoritmo greedy]]

# [[Ricerca locale (ottimizzazione)|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 popular relaxations include the following.

## Rilassamento della [[programmazione lineare]]

## Rilassamento della [[programmazione semidefinita]]