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

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

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

Наивная идея построения алгоритма аппроксимации для общего случая заключается в использовании леса, соединяющего все отверстия с границей, и последующем решении полученной задачи без отверстий за время <math>O(n^4)</math>. На основе этой идеи Лингас [10] предложил первую аппроксимацию с константными границами, коэффициент эффективности которой равен 41.

Начнем с прямолинейной плоскости с препятствиями, заданными в виде прямолинейных многоугольников. Пусть даны n точек на плоскости. Задача состоит в том, чтобы найти кратчайшее прямолинейное дерево Штейнера, соединяющее эти точки. Уже известно, что существует полиномиальная по времени схема аппроксимации для построения прямолинейного минимального дерева Штейнера без препятствий, которая может быть построена методом адаптивного разбиения с применением либо портальной, либо m-гильотинной техники разреза. Однако и m-гильотинный разрез, и метод портала не работают приналичии препятствий. Портальная методика неприменима, так как препятствия могут блокировать движение линии, пересекающей разрез в портале. Провести m-гильотинный разрез также не удается, поскольку препятствия могут разрушить сегмент разреза, обеспечивающий связность дерева Штейнера.

Несмотря на вышеизложенные факты, для RSMT с препятствиями все же могут существовать схемы аппроксимации с полиномиальным временем выполнения. Сильное доказательство этого тезиса было получено в работе Мина и др. [11]. Авторы построили полиномиальную по времени схему аппроксимации для задачи с препятствиями при условии, что отношение самого длинного и самого короткого ребер [[минимальное остовное дерево|минимального остовного дерева]] ограничено константой. Эта схема основывается на классическом неадаптивном подходе к разбиению. Все вышесказанное позволяет предположить, что для случая с препятствиями может быть найден новый адаптивный метод.