Metraipolis › archive › dc_fb0563e25110

Algoritmo di approssimazione — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/Algoritmo_di_approssimazione
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T21:56:55.560Z
SHA-256 of the archived text
fc8a3faed5023b1d275e5324652b2448daa4e58177e05b66d7d46a7a2bdd1e10
Stable URL of this page
https://metraipolis.com/documento/dc_fb0563e25110

How to cite

Algoritmo di approssimazione — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Algoritmo_di_approssimazione (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_fb0563e25110 (Metraipolis archive dc_fb0563e25110, sha256 fc8a3faed5023b1d275e5324652b2448daa4e58177e05b66d7d46a7a2bdd1e10)
BibTeX
@misc{dcfb0563e25110,
  title = {Algoritmo di approssimazione — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Algoritmo_di_approssimazione},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_fb0563e25110; sha256 fc8a3faed5023b1d275e5324652b2448daa4e58177e05b66d7d46a7a2bdd1e10},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Algoritmo_di_approssimazione. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Nell'informatica e nella ricerca operativa, un algoritmo di approssimazione è un algoritmo usato per trovare soluzioni approssimate a problemi di ottimizzazione. Gli algoritmi di approssimazione sono spesso associati a problemi 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 copertura dei vertici nei 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 P = NP, come il problema della massima cricca. I problemi NP-difficili spesso possono essere espressi come 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/semidefiniti, 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(n2000). 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 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 

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «ottimizzazione (matematica)»).
Fonte: Wikipedia in italiano, voce «Algoritmo di approssimazione» — https://it.wikipedia.org/wiki/Algoritmo_di_approssimazione
Wikidata Q621751 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q621751
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Algoritmo_di_approssimazione?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 151559361, consultata il 2026-10-07T21:34:26.175Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: a2e684df8fcf8940dfd0df50712cef29fc836b613f14c534b3107a0358916899