Обрезка и поиск - Википедия - Prune and search

Обрезка и поиск это метод решения оптимизация проблемы, предложенные Нимрод Мегиддо в 1983 г.[1]

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

Это похоже на повторение бинарный поиск но имеет больший S(п) термин, чем постоянный термин двоичного поиска. В алгоритмах сокращения и поиска S (n) обычно как минимум линейный (так как весь ввод должен быть обработан). При таком предположении рекуррентность имеет решение Т(п) = О (S(п)). В этом можно убедиться, применив основная теорема для повторений "разделяй и властвуй" или наблюдая, что времена для рекурсивных подзадач уменьшаются в геометрическая серия.

В частности, сам Мегиддо использовал этот подход в своих линейное время алгоритм для линейное программирование проблема, когда размер фиксирован[2] и для минимальная ограничивающая сфера проблема для множества точек в пространстве.[1]

Рекомендации

  1. ^ а б Н. Мегиддо. Алгоритмы линейного времени для линейного программирования в R3 и связанные с этим проблемы. SIAM J. Comput., 12: 759–776, 1983.
  2. ^ Нимрод Мегиддо, Линейное программирование в линейном времени, когда размерность фиксирована, 1984