Algoritmo di approssimazione: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m nuova chiave d'ordine per Categoria:Algoritmi: "Approssimazione" usando HotCat |
Funzionalità collegamenti suggeriti: 2 collegamenti inseriti. |
||
| (Una versione intermedia di un altro utente non mostrate) | |||
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''<sup>2000</sup>). 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 86:
==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''].
| |||