4551
правка
Адаптивные разбиения: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
Под влиянием работы [ ], посвященной применению динамического программирования к оптимальным деревьям маршрутизации, Ду и коллеги [5] предложили идею адаптивного разбиения. Для разбиения прямоугольника они использовали последовательность гильотинных разрезов; каждый гильотинный разрез разбивает связную область не менее чем на две части. С помощью динамического программирования им удалось показать, что прямоугольное гильотинное разбиение минимальной длины (т. е. имеющее минимальную общую длину среди всех гильотинных разбиений) может быть вычислено за время <math>O(n^5)</math>. Поэтому они предложили использовать для аппроксимации MELRP прямоугольное гильотинное разбиение минимальной длины и попытались проанализировать коэффициент эффективности. К сожалению, получить постоянный коэффициент в общем случае им не удалось, а верхняя граница 2 для коэффициента эффективности была получена только в NP-полном частном случае [7]. В этом частном случае на вход подается прямоугольник с несколькими точками внутри, которые являются отверстиями. Ниже приводится упрощенная версия доказательства, полученного Ду и др. [6]. | Под влиянием работы [4], посвященной применению динамического программирования к оптимальным деревьям маршрутизации, Ду и коллеги [5] предложили идею адаптивного разбиения. Для разбиения прямоугольника они использовали последовательность гильотинных разрезов; каждый гильотинный разрез разбивает связную область не менее чем на две части. С помощью динамического программирования им удалось показать, что прямоугольное гильотинное разбиение минимальной длины (т. е. имеющее минимальную общую длину среди всех гильотинных разбиений) может быть вычислено за время <math>O(n^5)</math>. Поэтому они предложили использовать для аппроксимации MELRP прямоугольное гильотинное разбиение минимальной длины и попытались проанализировать коэффициент эффективности. К сожалению, получить постоянный коэффициент в общем случае им не удалось, а верхняя граница 2 для коэффициента эффективности была получена только в NP-полном частном случае [7]. В этом частном случае на вход подается прямоугольник с несколькими точками внутри, которые являются отверстиями. Ниже приводится упрощенная версия доказательства, полученного Ду и др. [6]. | ||
| Строка 35: | Строка 35: | ||
Если сегмент является вертикальным, то | Если сегмент является вертикальным, то <math>proj_x (P) = 0</math> и, следовательно, <math>guil(P) < 2 \cdot length(P) - proj_x(P)</math>. | ||
Теперь рассмотрим вариант k > | Теперь рассмотрим вариант <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>. Заметим, что guil(P) < guil(P1) + guil(P2) + a ; length(P) = length(P1) + length(P2) + length(s) ; projx(P) = projx(P1) + projx(P2): | |||
Случай 1. Существует вертикальный сегмент s, длина которого больше или равна 0 | |||
Следовательно, guil(P) < 2- length(P) - projx(P): | Следовательно, guil(P) < 2- length(P) - projx(P): | ||