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

Впервые адаптивное разбиение было введено в конструкцию приближенного алгоритма Ду и др. [5] с помощью гильотинного разреза при изучении задачи о прямоугольном разбиении с минимальной длиной ребра (MELRP). Авторы обнаружили, что если разбиение выполняется последовательностью гильотинных разрезов, то оптимальное решение может быть вычислено за полиномиальное время с помощью динамического программирования. Более того, это оптимальное решение можно использовать как достаточно хорошее приближенное решение для исходной задачи прямоугольного разбиения. И Арора [1], и Митчелл и др. [12 , 13] выяснили, что разрез не обязательно должен быть полностью гильотинным. Другими словами, динамическое программирование по-прежнему может быть выполнено за полиномиальное время, если подзадачи имеют некоторые связи, но количество этих связей меньше. При увеличении числа связей полученное приближенное решение приближается к оптимальному, а время выполнения, естественно, увеличивается. Также было установлено, что данный метод может быть применен ко многим задачам геометрической оптимизации для получения схем аппроксимации с полиномиальным временем выполнения.