Algoritmo di approssimazione: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
m Bot: Fix portali in ordine alfabetico
Botcrux (discussione | contributi)
m Bot, replaced: Categoria:Complessità computazionale → Categoria:Teoria della complessità computazionale
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 69:
 
==Note==
<references/>
 
==Bibliografia==
Riga 91:
 
[[Categoria:Algoritmi]]
[[Categoria:ComplessitàTeoria della complessità computazionale]]
[[Categoria:Matematica per l'informatica]]