Пређи на садржај

Корисник: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]

Референце

[уреди]
  1. 1,0 1,1 Nimrod Megiddo (1983) Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Comput., 12:759–776 doi:10.1109/SFCS.1982.24
  2. Nimrod Megiddo (1984)Linear Programming in Linear Time When the Dimension Is Fixed doi:10.1145/2422.322418