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

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