Algoritmo di approssimazione: differenze tra le versioni

Versione delle 10:08, 7 giu 2014

Versione attuale delle 16:58, 2 feb 2025

(7 versioni intermedie di 6 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 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.

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

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

==Garanzie di prestazione ==

Riga 56:

Ormai ci sono parecchie tecniche standard che si usano per progettare un algoritmo di approssimazione. Queste comprendono 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.

Riga 66:

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 arbitarioarbitrario ϵ > 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.

==Note==

<references/>

==Bibliografia==

Riga 83:

* [[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–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à}}

{{Portale|Informatica|Matematica}}

[[Categoria:Algoritmi|Approssimazione]]

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

[[Categoria:Matematica per l'informatica]]