Algoritmo di approssimazione: differenze tra le versioni

Versione delle 00:22, 23 mar 2014

Versione delle 00:39, 23 mar 2014

Riga 1:

{{T|inglese|informatica|marzo 2014}}

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ù per problemi dove gli algoritmi esatti in tempo polinomiale sono noti ma risultano troppo costosi a causa della dimensione dell'input.

Riga 64 ⟶ 62:

## Rilassamento della [[programmazione semidefinita]]

# Incorporare il problema in qualche metrica semplice e poi risolverlo sulla metrica. Questa è conosciuta anche come incoporazione metrica.

<!--

== Termini epsilon ==

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]] doutodovuto 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 casacaso, il rapporto di approssimazione è ''c'' ∓ ''k'' / OPT = ''c'' ∓ o(1) per alcune costanti ''c'' e ''k''. Dato un arbitario ϵ > 0, onesi canpuò choosescegliere a large enoughun ''N'' suchgrande thatabbastanza thetale termche il termine ''k'' / OPT < ϵ forper everyogni ''n ≥ N''. ForPer every fixedogni ϵ fisso, instancesle ofistanze sizedi dimensione ''n < N'' canpossono beessere solvedrisolte bymediante brutela force[[Metodo forza bruta|forza bruta]], therebymostrando showingin antal approximationmodo ratioun rapporto di approssimazione — existenceesistenza ofdi approximationalgoritmi algorithmsdi approssimazione withcon auna guaranteegaranzia — ofdi ''c'' ∓ ϵ forper everyogni ϵ > 0.

-->

==Note==