Корисник:Св4и8/превод1

Метод сечења и претраге

Метода сечења и претраге (prune and search) је метода за решавање оптимизационих проблема коју је предложио Нимрод Мегидо 1983. године.

Основна идеја ове методе је рекурзивни поступак у коме се у сваком кораку величина улаза смањује („сече“) за константан фактор 0 < p < 1. Стога је то облик алгоритма смањи и покори (decrease and conquer), где је смањење у сваком кораку константно.

Нека је n величина улаза, T(n) временска сложеност целог алгоритма сечења и претраге, а S(n) временска сложеност корака сечења. Тада T(n) задовољава следећу релацију:

        T(n)=S(n)+T(n(1−p)).

Ова релација подсећа на релацију за бинарну претрагу, али има већи S(n) члан од константног члана у бинарној претрази. У алгоритмима „сечења и претраге“, S(n) је обично барем линеарно (јер је потребно обрадити цео улаз). Са овом претпоставком, решење релације је T(n) = O(S(n)). Ово се може показати применом мастер теореме за релације поделе и покоравања или посматрањем да се времена за рекурзивне потпроблеме смањују у геометријској серији.

Посебно, сам Мегидо је користио овај приступ у свом алгоритму линеарне сложености за проблем линеарног програмирања када је димензија фиксна, као и за проблем минималне сфере која обухвата скуп тачака у простору.