Korisnik:Sv4i8/prevod1
Metod sečenja i pretrage
[uredi]Metoda sečenja i pretrage (prune and search) je metoda za rešavanje optimizacionih problema koju je predložio Nimrod Megido 1983. godine.[1]
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:
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[2], kao i za problem minimalne sfere koja obuhvata skup tačaka u prostoru.[1]