Prune and search: differenze tra le versioni

Versione delle 01:15, 6 set 2014

Versione attuale delle 09:29, 29 giu 2025

(6 versioni intermedie di 4 utenti non mostrate)

Riga 1:

{{S|algoritmi}}

'''Prune and search''' (in [[Lingua italiana|italiano]] "sfoltisci e cerca") è un metodo per risolvere problemi di [[Ottimizzazione (matematica)|ottimizzazione]] ideato da [[Nimrod Megiddo]] nel 1983.<ref name=lp3>N. Megiddo. Linear-time algorithms for linear programming in R³ and related problems. SIAM J. Computing, 12:759–776, 1983.</ref>

L'idea alla base del metodo è una [[Ricorsione|procedura ricorsiva]], ad ogni passo della quale la taglia dell'input è ridotta (''prune'') di un fattore costante <math>0<p<1</math>. Esso è dunque un algoritmo del tipo [[Divide et impera (informatica)|divide et impera]]. Sia <math>n</math> la taglia dell'input, <math>T(n)</math> sarà la [[complessità temporale]] di tutto l'algoritmo e <math>S(n)</math> la complessità temporale dell'operazione di sfoltimento, allora <math>T(n)</math> obbedirà alla seguente [[relazione di ricorrenza]]:

Riga 5 ⟶ 6:

:<math>T(n) = S(n) + T(n(1-p)), \, </math>

che hasi comepuò provare, col [[metodo di Akra-Bazzi]], avere soluzione <math>T(n) = O(1+\int_1^x \frac {S(nu)}{u} du)</math>, dato che il secondo addendo è una [[serie geometrica]] equivalente ase <math>1/|S'(1-(1-p)n)| = 1/pO(x^c)</math>, (edove nellac notazioneè [[O-grande]]una le costanti additive e moltiplicative vengono trascurate)costante.

<!--

Riga 12 ⟶ 13:

== Note ==

{{<references}}/>

== Voci correlate ==