Korisnik:Sv4i8/prevod1

Metod sečenja i pretrage

Metoda sečenja i pretrage (prune and search) je metoda za rešavanje optimizacionih problema koju je predložio Nimrod Megido 1983. godine.

Osnovna ideja ove metode je rekurzivni postupak u kome se u svakom koraku veličina ulaza smanjuje („seče“) za konstantan faktor 0 < p < 1. Stoga je to oblik algoritma smanji i pokori (decrease and conquer), gde je smanjenje u svakom koraku konstantno.

Neka je n veličina ulaza, T(n) vremenska složenost celog algoritma sečenja i pretrage, a S(n) vremenska složenost koraka sečenja. Tada T(n) zadovoljava sledeću relaciju:

$T(n)=S(n)+T(n(1-p)).$

Ova relacija podseća na relaciju za binarnu pretragu, ali ima veći S(n) član od konstantnog člana u binarnoj pretrazi. U algoritmima „sečenja i pretrage“, S(n) je obično barem linearno (jer je potrebno obraditi ceo ulaz). Sa ovom pretpostavkom, rešenje relacije je T(n) = O(S(n)). Ovo se može pokazati primenom master teoreme za relacije podele i pokoravanja ili posmatranjem da se vremena za rekurzivne potprobleme smanjuju u geometrijskoj seriji.

Posebno, sam Megido je koristio ovaj pristup u svom algoritmu linearne složenosti za problem linearnog programiranja kada je dimenzija fiksna, kao i za problem minimalne sfere koja obuhvata skup tačaka u prostoru.