4446
правок
Адаптивные разбиения: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
Развивая направления исследований работы [4], посвященной применению динамического программирования к оптимальным деревьям маршрутизации, Ду и коллеги [5] предложили идею адаптивного разбиения. Для разбиения прямоугольника они использовали последовательность гильотинных разрезов; каждый гильотинный разрез разбивает связную область не менее чем на две части. С помощью динамического программирования им удалось показать, что прямоугольное гильотинное разбиение минимальной длины (т. е. имеющее минимальную общую длину среди всех гильотинных разбиений) может быть вычислено за время <math>O(n^5)</math>. Поэтому они предложили использовать для аппроксимации MELRP прямоугольное гильотинное разбиение минимальной длины и попытались проанализировать коэффициент эффективности. К сожалению, получить постоянный коэффициент в общем случае им не удалось, а верхняя граница 2 для коэффициента эффективности была получена только в NP-полном частном случае [7]. В этом частном случае на вход подается прямоугольник с несколькими точками внутри, которые являются отверстиями. Ниже приводится упрощенная версия доказательства, полученного Ду и др. [6]. | |||
| Строка 29: | Строка 29: | ||
Мы говорим, что прямоугольное разбиение покрывается гильотинным разбиением, если каждый сегмент (отрезок) прямоугольного разбиения покрывается гильотинным разрезом последнего. Обозначим за <math>guil(P)</math> минимальную длину гильотинного разбиения, покрывающего P, а за <math>length(P)</math> – общую длину прямоугольного разбиения P. Путем индукции по числу k сегментов в P можно доказать, что <math>guil(P) \le 2 \cdot length(P) - proj_x(P)</math>: | |||
| Строка 39: | Строка 39: | ||
Теперь рассмотрим вариант <math>k \ge 2</math>. Предположим, что в исходном прямоугольнике каждое вертикальное ребро имеет длину <math>a</math>, а каждое горизонтальное – длину <math>b</math>. Рассмотрим два случая: | Теперь рассмотрим вариант <math>k \ge 2</math>. Предположим, что в исходном прямоугольнике каждое вертикальное ребро имеет длину <math>a</math>, а каждое горизонтальное – длину <math>b</math>. Рассмотрим два случая: | ||
''Случай 1''. Существует вертикальный сегмент s, длина которого больше или равна <math>0,5 a</math>. Применим гильотинный разрез вдоль этого сегмента s. Тогда остаток P разделится на две части <math>P_1</math> и <math>P_2</math>, которые образуют прямоугольное разбиение двух получившихся маленьких прямоугольников, соответственно. По предположению индукции, <math>guil(P_i) \le 2 \cdot length(P_i) - proj_x(P_i)</math> для <math>i = 1, 2</math>. Заметим, что | ''Случай 1''. Существует вертикальный сегмент s, длина которого больше или равна <math>0,5 a</math>. Применим гильотинный разрез вдоль этого сегмента s. Тогда остаток P разделится на две части <math>P_1</math> и <math>P_2</math>, которые образуют прямоугольное разбиение двух получившихся маленьких прямоугольников, соответственно. По предположению индукции, <math>guil(P_i) \le 2 \cdot length(P_i) - proj_x(P_i)</math> для <math>i = 1, 2</math>. Заметим, что | ||
| Строка 51: | Строка 52: | ||
Случай 2. Не существует вертикального сегмента s, длина которого больше или равна <math>0,5 a</math>. Выберем горизонтальный гильотинный разрез, который разбивает прямоугольник на две равные части. Обозначим за <math>P_1</math> и <math>P_2</math> две части, полученные в результате разбиения прямоугольника P. По предположению индукции, <math>guil(P_i) \le 2 \cdot length(P_i) - proj_x(P_i)</math> для <math>i = 1, 2</math>. Заметим, что | ''Случай 2''. Не существует вертикального сегмента s, длина которого больше или равна <math>0,5 a</math>. Выберем горизонтальный гильотинный разрез, который разбивает прямоугольник на две равные части. Обозначим за <math>P_1</math> и <math>P_2</math> две части, полученные в результате разбиения прямоугольника P. По предположению индукции, <math>guil(P_i) \le 2 \cdot length(P_i) - proj_x(P_i)</math> для <math>i = 1, 2</math>. Заметим, что | ||
<math>guil(P) = guil(P_1) + guil(P_2) + b</math>, | <math>guil(P) = guil(P_1) + guil(P_2) + b</math>, | ||
