Prune and search

Prune and search (in italiano "sfoltisci e cerca") è un metodo per risolvere problemi di ottimizzazione ideato da Nimrod Megiddo nel 1983.^[1]

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

${\displaystyle T(n)=S(n)+T(n(1-p)),\,}$

che si può provare, col metodo di Akra-Bazzi, avere soluzione ${\displaystyle T(n)=O(1+\int _{1}^{x}{\frac {S(u)}{u}}du)}$, se ${\displaystyle |S'(n)|=O(x^{c})}$, dove c è una costante.

Note

1. ^ N. Megiddo. Linear-time algorithms for linear programming in R³ and related problems. SIAM J. Computing, 12:759–776, 1983.

Voci correlate

• Divide et impera (informatica)

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica