Обрезка и поиск - Prune and search
Обрезка и поиск это метод решения оптимизация проблемы, предложенные Нимрод Мегиддо в 1983 г.[1]
Основная идея метода - рекурсивная процедура, в которой на каждом шаге размер входных данных уменьшается («сокращается») на постоянный коэффициент. 0 < п < 1. Таким образом, это форма алгоритм уменьшения и победы, где на каждом шаге уменьшение происходит в постоянный коэффициент. Позволять п быть размером ввода, Т(п) быть временная сложность всего алгоритма prune-and-search, и S(п) быть временной сложностью этапа обрезки. потом Т(п) подчиняется следующим отношение повторения:
Это похоже на повторение бинарный поиск но имеет больший S(п) термин, чем постоянный термин двоичного поиска. В алгоритмах сокращения и поиска S (n) обычно как минимум линейный (так как весь ввод должен быть обработан). При таком предположении рекуррентность имеет решение Т(п) = О (S(п)). В этом можно убедиться, применив основная теорема для повторений "разделяй и властвуй" или наблюдая, что времена для рекурсивных подзадач уменьшаются в геометрическая серия.
В частности, сам Мегиддо использовал этот подход в своих линейное время алгоритм для линейное программирование проблема, когда размер фиксирован[2] и для минимальная ограничивающая сфера проблема для множества точек в пространстве.[1]