Корисник:Sv4i8/превод1
Метод сечења и претраге
[уреди]Метода сечења и претраге (prune and search) је метода за решавање оптимизационих проблема коју је предложио Нимрод Мегидо 1983. године.[1]
Основна идеја ове методе је рекурзивни поступак у коме се у сваком кораку величина улаза смањује („сече“) за константан фактор 0 < p < 1. Стога је то облик алгоритма смањи и покори (decrease and conquer), где је смањење у сваком кораку константно.
Нека је n величина улаза, T(n) временска сложеност целог алгоритма сечења и претраге, а S(n) временска сложеност корака сечења. Тада T(n) задовољава следећу релацију:
Ова релација подсећа на релацију за бинарну претрагу, али има већи S(n) члан од константног члана у бинарној претрази. У алгоритмима „сечења и претраге“, S(n) је обично барем линеарно (јер је потребно обрадити цео улаз). Са овом претпоставком, решење релације је T(n) = O(S(n)). Ово се може показати применом мастер теореме за релације поделе и покоравања или посматрањем да се времена за рекурзивне потпроблеме смањују у геометријској серији.
Посебно, сам Мегидо је користио овај приступ у свом алгоритму линеарне сложености за проблем линеарног програмирања када је димензија фиксна[2], као и за проблем минималне сфере која обухвата скуп тачака у простору.[1]