Базовый набор
В вычислительной геометрии базовый набор — это небольшой набор точек, который аппроксимирует форму большего набора точек в том смысле, что применение некоторой геометрической меры к двум наборам (например, ограничивающей рамки минимальному объему ) приводит к примерно равным числам. Многие задачи естественной геометрической оптимизации имеют базовые наборы, которые аппроксимируют оптимальное решение с точностью до коэффициента 1 + ε , которые могут быть найдены быстро (за линейное или почти линейное время) и имеют размер, ограниченный функцией 1/ ε, независимой от входного размера, где ε — произвольное положительное число. В этом случае получается схема аппроксимации с линейным или почти линейным временем, основанная на идее нахождения основного набора и последующего применения к нему точного алгоритма оптимизации. Независимо от того, насколько медленным является точный алгоритм оптимизации, для любого фиксированного выбора ε время работы этой аппроксимационной схемы будет равно O (1) плюс время нахождения набора ядер. [1] [2]
Ссылки
[ редактировать ]- ^ Агарвал, Панкадж К .; Хар-Пелед, Сариэль ; Варадараджан, Кастури Р. (2005), «Геометрическая аппроксимация с помощью наборов ядер» , в Гудмане, Джейкоб Э .; Пах, Янош ; Вельцль, Эмо (ред.), Комбинаторная и вычислительная геометрия , Публикации НИИ математических наук, том. 52, Кембриджский университет. Press, Cambridge, стр. 1–30, MR 2178310 .
- ^ Нильсен, Франк (2016). «10. Быстрая приближенная оптимизация в больших размерностях с использованием базовых наборов и быстрое уменьшение размерностей» . Введение в HPC с MPI для науки о данных . Спрингер. стр. 259–272. ISBN 978-3-319-21903-5 .
 | Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее . |