Pruneți și căutați

Prune și căutare (în italiană „thin and search”) este o metodă de rezolvare a problemelor de optimizare concepută de Nimrod Megiddo în 1983. ^[1]

Ideea din spatele metodei este o procedură recursivă , la fiecare etapă a cărei dimensiune a intrării este redusă ( prune ) cu un factor constant ${\displaystyle 0<semantics><mrow class=$ ${\ displaystyle 0 <p <1}$ ${\ displaystyle 0 <p <1}$ . Prin urmare, este un algoritm de divizare și cucerire . Este $n$ ${\ displaystyle n}$ $n$ dimensiunea intrării, $T(n)$ ${\ displaystyle T (n)}$ $T (n)$ va fi complexitatea în timp a întregului algoritm e $S(n)$ ${\ displaystyle S (n)}$ ${\ displaystyle S (n)}$ complexitatea în timp a operației de subțiere, atunci $T(n)$ ${\ displaystyle T (n)}$ $T (n)$ va respecta următoarea relație de recurență :

T(n)=S(n)+T(n(1-p)),\,

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

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

că se poate dovedi, cu metoda Akra-Bazzi , că are o soluție $T(n)=O(1+\int _{1}^{x}{\frac {S(u)}{u}}du)$ ${\ displaystyle T (n) = O (1+ \ int _ {1} ^ {x} {\ frac {S (u)} {u}} du)}$ ${\ displaystyle T (n) = O (1+ \ int _ {1} ^ {x} {\ frac {S (u)} {u}} du)}$ , de sine $|S'(n)|=O(x^{c})$ ${\ displaystyle | S '(n) | = O (x ^ {c})}$ ${\ displaystyle | S '(n) | = O (x ^ {c})}$ , unde c este o constantă.

Notă

^ N. Megiddo. Algoritmi în timp liniar pentru programarea liniară în R ³ și probleme conexe. SIAM J. Computing, 12: 759–776, 1983.

Elemente conexe

Divide et impera (informatică)

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

[lp3-1] N. Megiddo. Algoritmi în timp liniar pentru programarea liniară în R ³ și probleme conexe. SIAM J. Computing, 12: 759–776, 1983.

[1]