Algoritmo di approssimazione: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Inizio traduzione |
Nessun oggetto della modifica |
||
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.
<!--▼
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 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 [[Classi di complessità P e NP|P = NP]], come il [[problema della massima cricca]].
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.
▲<!--
Not all approximation algorithms are suitable for all practical applications. They often use IP/LP/[[semidefinite programming|Semidefinite]] solvers, complex data structures or sophisticated algorithmic techniques which lead to difficult implementation problems. Also, some approximation algorithms have impractical running times even though they are polynomial time, for example O(''n''<sup>2000</sup>). Yet the study of even very expensive algorithms is not a completely theoretical pursuit as they can yield valuable insights. A classic example is the initial PTAS for [[Euclidean traveling salesman problem|Euclidean TSP]] due to [[Sanjeev Arora]] which had prohibitive running time, yet within a year, Arora refined the ideas into a linear time algorithm. Such algorithms are also worthwhile in some applications where the running times and cost can be justified e.g. [[computational biology]], [[financial engineering]], [[transportation planning]], and [[inventory management]]. In such scenarios, they must compete with the corresponding direct IP formulations.
Riga 69:
An ϵ-term may appear when an approximation algorithm introduces a multiplicative error and a constant error while the minimum optimum of instances of size ''n'' goes to infinity as ''n'' does. In this case, the approximation ratio is ''c'' ∓ ''k'' / OPT = ''c'' ∓ o(1) for some constants ''c'' and ''k''. Given arbitrary ϵ > 0, one can choose a large enough ''N'' such that the term ''k'' / OPT < ϵ for every ''n ≥ N''. For every fixed ϵ, instances of size ''n < N'' can be solved by brute force , thereby showing an approximation ratio — existence of approximation algorithms with a guarantee — of ''c'' ∓ ϵ for every ϵ > 0.
-->▼
==Note==▼
<references/> ▼
==
▲* {{cite book
▲ | last = Vazirani
▲ | first = Vijay V.
▲ | authorlink = Vijay Vazirani
▲ | title = Approximation Algorithms
▲ | publisher = Springer
▲ | year = 2003
▲ | ___location = Berlin
| isbn = 3-540-65367-8 }}
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]],
* [[Dorit H. Hochbaum]]
* {{
==
* Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, [[Marek Karpinski]]
▲-->
▲==Note==
▲<references/>
{{Portali|Matematica|Informatica}}
[[Categoria:Algoritmi]]
[[Categoria:Complessità computazionale]]
[[Categoria:Matematica per l'informatica]]
|