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

Задача MELRP была предложена Лингасом и др. [ ] в следующей формулировке. Пусть задан прямолинейный многоугольник (возможно, с несколькими прямоугольными отверстиями). Требуется разбить его на прямоугольники с минимальной суммарной длиной ребер. Каждое отверстие может быть вырождено в отрезок прямой или точку.

В работе [9] упоминается несколько возможных приложений данной задачи: управление процессами (сокращение запасов), системы автоматического проектирования топологии интегральных схем (определение каналов), архитектура (устройство внутренних перегородок между кабинетами). Естественной целью для этих задач является разбиение с минимальной длиной ребра, поскольку существует определенное количество отходов (например, опилок) или затрат (например, на перегородки в офисе), пропорциональных сумме длин проведенных ребер. При проектировании СБИС этот критерий используется в системе MIT Placement and Interconnect (PI) для разделения области маршрутизации на каналы, что позволяет получить большие «естественно выглядящие» каналы с минимальным взаимодействием между ними.

Авторы показали, что хотя MELRP в общем случае является недетерминированной задачей с полиномиальным временем выполнения (NP), в случае без отверстий она может быть решена за время O(n4), где n – число вершин входного прямолинейного многоугольника. Полиномиальный алгоритм, по существу, реализует подход динамического программирования, основанный на том, что всегда существует оптимальное решение, удовлетворяющее следующему свойству: каждая линия разреза проходит через вершину входного многоугольника или отверстия (то есть каждый максимальный отрезок разреза инцидентен вершине входного многоугольника или отверстиям).

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

Под влиянием работы [ ], посвященной применению динамического программирования к оптимальным деревьям маршрутизации, Ду и коллеги [5] предложили идею адаптивного разбиения. Для разбиения прямоугольника они использовали последовательность гильотинных разрезов; каждый гильотинный разрез разбивает связную область не менее чем на две части. С помощью динамического программирования им удалось показать, что прямоугольное гильотинное разбиение минимальной длины (т. е. имеющее минимальную общую длину среди всех гильотинных разбиений) может быть вычислено за время O(n5). Поэтому они предложили использовать для аппроксимации MELRP прямоугольное гильотинное разбиение минимальной длины и попытались проанализировать коэффициент эффективности. К сожалению, получить постоянный коэффициент в общем случае им не удалось, а верхняя граница 2 для коэффициента эффективности была получена только в NP-полном частном случае [7]. В этом частном случае на вход подается прямоугольник с несколькими точками внутри, которые являются отверстиями. Ниже приводится упрощенная версия доказательства, полученного Ду и др. [6].

Теорема. Прямоугольное гильотинное разбиение минимальной длины является аппроксимацией с коэффициентом эффективности 2 для задачи MELRP.

Доказательство. Рассмотрим прямоугольное разбиение P. Обозначим за projx (P) суммарную длину отрезков на горизонтальной прямой, покрываемых вертикальной проекцией разбиения P.

Прямоугольное разбиение покрывается гильотинным разбиением, если каждый сегмент (отрезок) прямоугольного разбиения покрывается гильотинным разрезом последнего. Обозначим за guil(P) минимальную длину гильотинного разбиения, покрывающего P, а за length(P) – общую длину прямоугольного разбиения P. Путем индукции по числу k сегментов в P будет доказано, что guil(P) <2-length(P)- projx(P):

Для k = 1 имеет место guil(P) = length(P). Если сегмент является горизонтальным, то projx(P) = length(P) и, следовательно, guil(P) = 2 - length(P) - projx(P):