4551
правка
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Адаптивное разбиение является одним из основных методов построения полиномиальных по времени алгоритмов аппроксимации, особенно полиномиальных схем аппроксимации для задач геометрической оптимизации. Суть метода заключается в том, что входные данные помещаются в прямоугольник, | Адаптивное разбиение является одним из основных методов построения полиномиальных по времени алгоритмов аппроксимации, особенно полиномиальных схем аппроксимации для задач геометрической оптимизации. Суть метода заключается в том, что входные данные помещаются в прямоугольник, который затем разбивается на меньшие прямоугольники последовательностью разрезов таким образом, что задача также разбивается на подзадачи. С каждым адаптивным разбиением можно рекурсивно построить выполнимое решение на основе решений от наименьших прямоугольников к большим. С помощью динамического программирования оптимальное адаптивное разбиение вычисляется за полиномиальное время. | ||
== История вопроса == | == История вопроса == |
правка