Адаптивные разбиения: различия между версиями

Перейти к навигации Перейти к поиску
м
Строка 3: Строка 3:


== Постановка задачи ==
== Постановка задачи ==
Адаптивное разбиение является одним из основных методов построения полиномиальных по времени алгоритмов аппроксимации, особенно полиномиальных схем аппроксимации для задач геометрической оптимизации. Суть метода заключается в том, что входные данные помещаются в прямоугольник, и он разбивается на меньшие прямоугольники последовательностью разрезов таким образом, что задача также разбивается на подзадачи. С каждым адаптивным разбиением можно рекурсивно построить выполнимое решение от решений в наименьших прямоугольниках к большим. С помощью динамического программирования оптимальное адаптивное разбиение вычисляется за полиномиальное время.
Адаптивное разбиение является одним из основных методов построения полиномиальных по времени алгоритмов аппроксимации, особенно полиномиальных схем аппроксимации для задач геометрической оптимизации. Суть метода заключается в том, что входные данные помещаются в прямоугольник, который затем разбивается на меньшие прямоугольники последовательностью разрезов таким образом, что задача также разбивается на подзадачи. С каждым адаптивным разбиением можно рекурсивно построить выполнимое решение на основе решений от наименьших прямоугольников к большим. С помощью динамического программирования оптимальное адаптивное разбиение вычисляется за полиномиальное время.


== История вопроса ==
== История вопроса ==
4551

правка

Навигация