Адаптивные разбиения
Ключевые слова и синонимы
Методика построения аппроксимации
Постановка задачи
Адаптивное разбиение является одним из основных методов построения полиномиальных по времени аппроксимационных алгоритмов, особенно полиномиальных аппроксимационных схем для задач геометрической оптимизации. Суть метода заключается в том, что входные данные помещаются в прямоугольник, который затем разбивается на меньшие прямоугольники последовательностью разрезов таким образом, что задача также разбивается на подзадачи. С каждым адаптивным разбиением можно рекурсивно построить выполнимое решение на основе решений от наименьших прямоугольников к большим. С помощью динамического программирования оптимальное адаптивное разбиение вычисляется за полиномиальное время.
История вопроса
Впервые адаптивное разбиение при конструировании приближенного алгоритма ввели Ду и коллеги [5], применившие его с помощью гильотинных разрезов при изучении задачи о прямоугольном разбиении с минимальной длиной ребра (MELRP). Авторы обнаружили, что если разбиение выполняется последовательностью гильотинных разрезов, то оптимальное решение может быть вычислено за полиномиальное время с помощью динамического программирования. Более того, это оптимальное решение можно использовать как достаточно хорошее приближенное решение для исходной задачи прямоугольного разбиения. И Арора [1], и Митчелл и др. [12, 13] выяснили, что разрез не обязательно должен быть полностью гильотинным. Другими словами, динамическое программирование по-прежнему может быть выполнено за полиномиальное время, если подзадачи сохраняют некоторые связи, но количество этих связей меньше исходного. При увеличении числа связей полученное приближенное решение становится ближе к оптимальному, а время выполнения, естественно, увеличивается. Также было установлено, что данный метод может быть применен ко многим задачам геометрической оптимизации для получения аппроксимационных схем с полиномиальным временем выполнения.
Основные результаты
Задача MELRP была предложена Лингасом и др. [9] в следующей формулировке. Пусть задан прямолинейный многоугольник (возможно, с несколькими прямоугольными отверстиями). Требуется разбить его на прямоугольники с минимальной суммарной длиной ребер. Каждое отверстие может быть вырождено в отрезок прямой или точку.
В работе [9] упоминается несколько возможных приложений данной задачи: управление процессами (сокращение запасов), системы автоматического проектирования топологии интегральных схем (определение каналов), архитектура (устройство внутренних перегородок между кабинетами). Естественной целью для этих задач является разбиение с минимальной длиной ребра, поскольку количество отходов (например, опилок) или затрат (например, на перегородки в офисе) пропорционально сумме длин проведенных ребер. При проектировании СБИС этот критерий используется в системе MIT Placement and Interconnect (PI) для разделения области маршрутизации на каналы, что позволяет получить большие «естественно выглядящие» каналы с минимальным взаимодействием между ними.
Авторы показали, что хотя MELRP в общем случае является недетерминированной задачей с полиномиальным временем выполнения (NP), в случае без отверстий она может быть решена за время [math]\displaystyle{ O(n^4) }[/math], где n – число вершин входного прямолинейного многоугольника. Полиномиальный алгоритм, по существу, реализует подход динамического программирования, основанный на том, что всегда существует оптимальное решение, удовлетворяющее следующему свойству: каждая линия разреза проходит через вершину входного многоугольника или отверстия (то есть каждый максимальный сегмент разреза инцидентен вершине входного многоугольника или отверстиям).
Наивная идея построения аппроксимационного алгоритма для общего случая заключается в использовании леса, соединяющего все отверстия с границей, и последующем решении полученной задачи без отверстий за время [math]\displaystyle{ O(n^4) }[/math]. На основе этой идеи Лингас [10] предложил первую аппроксимацию с константными границами, коэффициент эффективности которой равен 41.
Развивая направления исследований работы [4], посвященной применению динамического программирования к оптимальным деревьям маршрутизации, Ду и коллеги [5] предложили идею адаптивного разбиения. Для разбиения прямоугольника они использовали последовательность гильотинных разрезов; каждый гильотинный разрез разбивает связную область не менее чем на две части. С помощью динамического программирования им удалось показать, что прямоугольное гильотинное разбиение минимальной длины (т. е. имеющее минимальную общую длину среди всех гильотинных разбиений) может быть вычислено за время [math]\displaystyle{ O(n^5) }[/math]. Поэтому они предложили использовать для аппроксимации MELRP прямоугольное гильотинное разбиение минимальной длины и попытались проанализировать коэффициент эффективности. К сожалению, получить постоянный коэффициент в общем случае им не удалось, а верхняя граница 2 для коэффициента эффективности была получена только в NP-полном частном случае [7]. В этом частном случае на вход подается прямоугольник с несколькими точками внутри, которые являются отверстиями. Ниже приводится упрощенная версия доказательства, полученного Ду и др. [6].
Теорема. Прямоугольное гильотинное разбиение минимальной длины является аппроксимацией с коэффициентом эффективности 2 для задачи MELRP.
Доказательство. Рассмотрим прямоугольное разбиение P. Обозначим за [math]\displaystyle{ proj_x (P) }[/math] суммарную длину отрезков на горизонтальной прямой, покрываемых вертикальной проекцией разбиения P.
Мы говорим, что прямоугольное разбиение покрывается гильотинным разбиением, если каждый сегмент (отрезок) прямоугольного разбиения покрывается гильотинным разрезом последнего. Обозначим за [math]\displaystyle{ guil(P) }[/math] минимальную длину гильотинного разбиения, покрывающего P, а за [math]\displaystyle{ length(P) }[/math] – общую длину прямоугольного разбиения P. Путем индукции по числу k сегментов в P можно доказать, что [math]\displaystyle{ guil(P) \le 2 \cdot length(P) - proj_x(P) }[/math]:
Для k = 1 имеет место [math]\displaystyle{ guil(P) = length(P) }[/math]. Если сегмент является горизонтальным, то [math]\displaystyle{ proj_x(P) = length(P) }[/math] и, следовательно, [math]\displaystyle{ guil(P) = 2 \cdot length(P) - proj_x(P) }[/math].
Если сегмент является вертикальным, то [math]\displaystyle{ proj_x (P) = 0 }[/math] и, следовательно, [math]\displaystyle{ guil(P) \lt 2 \cdot length(P) - proj_x(P) }[/math].
Теперь рассмотрим вариант [math]\displaystyle{ k \ge 2 }[/math]. Предположим, что в исходном прямоугольнике каждое вертикальное ребро имеет длину [math]\displaystyle{ a }[/math], а каждое горизонтальное – длину [math]\displaystyle{ b }[/math]. Рассмотрим два случая:
Случай 1. Существует вертикальный сегмент s, длина которого больше или равна [math]\displaystyle{ 0,5 a }[/math]. Применим гильотинный разрез вдоль этого сегмента s. Тогда остаток P разделится на две части [math]\displaystyle{ P_1 }[/math] и [math]\displaystyle{ P_2 }[/math], которые образуют прямоугольное разбиение двух получившихся маленьких прямоугольников, соответственно. По предположению индукции, [math]\displaystyle{ guil(P_i) \le 2 \cdot length(P_i) - proj_x(P_i) }[/math] для [math]\displaystyle{ i = 1, 2 }[/math]. Заметим, что
[math]\displaystyle{ guil(P) \le guil(P_1) + guil(P_2) + a }[/math],
[math]\displaystyle{ length(P) = length(P_1) + length(P_2) + length(s) }[/math],
[math]\displaystyle{ proj_x(P) = proj_x(P_1) + proj_x(P_2) }[/math].
Следовательно, [math]\displaystyle{ guil(P) \le 2 \cdot length(P) - proj_x(P) }[/math].
Случай 2. Не существует вертикального сегмента s, длина которого больше или равна [math]\displaystyle{ 0,5 a }[/math]. Выберем горизонтальный гильотинный разрез, который разбивает прямоугольник на две равные части. Обозначим за [math]\displaystyle{ P_1 }[/math] и [math]\displaystyle{ P_2 }[/math] две части, полученные в результате разбиения прямоугольника P. По предположению индукции, [math]\displaystyle{ guil(P_i) \le 2 \cdot length(P_i) - proj_x(P_i) }[/math] для [math]\displaystyle{ i = 1, 2 }[/math]. Заметим, что
[math]\displaystyle{ guil(P) = guil(P_1) + guil(P_2) + b }[/math],
[math]\displaystyle{ length(P) \ge length(P_1) + length(P_2) }[/math],
[math]\displaystyle{ proj_x(P) = proj_x(P_1) = proj_x(P_2) = b }[/math].
Следовательно, [math]\displaystyle{ guil(P) \le 2 \cdot length(P) - proj_x(P) }[/math].
Гонсалес и Чжэн [8] улучшили эту верхнюю границу до 1,75 и предположили, что коэффициент эффективности в данном случае равен 1,5.
Применение
В 1996 году Арора [1] и Митчелл и др. [12, 13, 14] обнаружили, что для того, чтобы получить вычислимое за полиномиальное время оптимальное решение для такой последовательности разрезов, разрез не обязательно должен быть полностью гильотинным. Конечно, количество связей, остающихся после неполного гильотинного разреза, должно быть ограничено. Митчелл и коллеги разработали технику m-гильотинного разбиения, тогда как Арора применил технологию «портала». Исследователи также обнаружили, что их методы могут быть использованы не только для MELRP, но и для многих задач геометрической оптимизации [1, 2, 3, 12, 13, 14, 15].
Открытые вопросы
На важном субмикронном этапе технологической эволюции в электронике именно межсоединения стали доминирующим фактором, определяющим производительность и надежность СБИС. Исторически сложилось так, что задача проектирования межсоединений в СБИС была очень тесно переплетена с классической задачей вычислительной геометрии – построением минимального дерева Штейнера. Некоторые важнейшие характеристики СБИС примерно пропорциональны длине межсоединений. К таким характеристикам относятся площадь кристалла, выход годных кристаллов, энергопотребление, надежность и синхронизация. Например, площадь, занимаемая межсоединениями, пропорциональна их суммарной длине и напрямую влияет на размер чипа. Увеличение размера микросхемы приводит к снижению процента выхода годных и росту стоимости производства. С увеличением длины проводов возрастает и стоимость других компонентов, необходимых для производства. С точки зрения производительности более длинные межсоединения ведут к увеличению рассеивания мощности, ухудшению синхронизации и другим нежелательным последствиям. Именно поэтому поиск минимальной длины межсоединений, согласующейся с другими целями и ограничениями, является настолько серьезной задачей на данном этапе развития технологии СБИС.
Совокупная длина межсоединений на микросхеме представляет собой сумму длин отдельных сигнальных сетей. Каждая сигнальная сеть представляет собой набор электрически связанных выводов, где один из выводов выступает в роли формирователя электрических сигналов, а другие являются их приемниками. Исторически сложилось так, что при поиске оптимальной конфигурации межсоединений выводы рассматривались как точки на плоскости, а задача маршрутизации отдельных сетей формулировалась как классическая задача построения минимального дерева Штейнера. По ряду причин технология СБИС реализует только прямолинейную разводку на множестве параллельных плоскостей – и, соответственно, за редким исключением, в области СБИС рассматривается только прямолинейный вариант дерева Штейнера. Эта формулировка известна как задача о прямолинейном минимальном дереве Штейнера (RSMT).
Последующее развитие технологии СБИС привело к тому, что при выборе топологий маршрутизации большое значение приобрели не только длина межсоединений, но и другие факторы. Например, наличие препятствий заставило пересмотреть методики, используемые при исследовании прямолинейного дерева Штейнера, поскольку многие классические методы в этих условиях не работают. Для пояснения вышеприведенного утверждения рассмотрим построение прямолинейного минимального дерева Штейнера при наличии препятствий.
Начнем с прямолинейной плоскости с препятствиями, заданными в виде прямолинейных многоугольников. Пусть даны n точек на плоскости. Задача состоит в том, чтобы найти кратчайшее прямолинейное дерево Штейнера, соединяющее эти точки. Уже известно, что существует полиномиальная по времени аппроксимационная схема для построения прямолинейного минимального дерева Штейнера без препятствий, которая может быть построена методом адаптивного разбиения с применением либо портальной, либо m-гильотинной техники разреза. Однако и m-гильотинный разрез, и метод портала не работают приналичии препятствий. Портальная методика неприменима, так как препятствия могут блокировать движение линии, пересекающей разрез в портале. Провести m-гильотинный разрез также не удается, поскольку препятствия могут разрушить сегмент разреза, обеспечивающий связность дерева Штейнера.
Несмотря на вышеизложенные факты, для RSMT с препятствиями все же могут существовать аппроксимационные схемы с полиномиальным временем выполнения. Сильное доказательство этого тезиса было получено в работе Мина и др. [11]. Авторы построили полиномиальную по времени аппроксимационную схему для задачи с препятствиями при условии, что отношение самого длинного и самого короткого ребер минимального остовного дерева ограничено константой. Эта схема основывается на классическом неадаптивном подходе к разбиению. Все вышесказанное позволяет предположить, что для случая с препятствиями может быть найден новый адаптивный метод.
См. также
Литература
1. Arora, S.: Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. In: Proc. 37th IEEE Symp. on Foundations of Computer Science, 1996, pp. 2-12
2. Arora, S.: Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In: Proc. 38th IEEE Symp. on Foundations of Computer Science, 1997, pp. 554-563
3. Arora, S.: Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. J. ACM 45, 753-782(1998)
4. Du, D.Z., Hwang, F.K., Shing, M.T., Witbold, T.: Optimal routing trees. IEEE Trans. Circuits 35,1335-1337 (1988)
5. Du, D.-Z., Pan, L.-Q., Shing, M.-T.: Minimum edge length guillotine rectangular partition. Technical Report 0241886, Math. Sci. Res. Inst., Univ. California, Berkeley (1986)
6. Du, D.-Z., Hsu, D.F., Xu, K.-J.: Bounds on guillotine ratio. Congressus Numerantium 58, 313-318 (1987)
7. Gonzalez, T., Zheng, S.Q.: Bounds for partitioning rectilinear polygons. In: Proc. 1st Symp. on Computational Geometry (1985)
8. Gonzalez, T., Zheng, S.Q.: Improved bounds for rectangular and guillotine partitions. J. Symb. Comput. 7, 591-610 (1989)
9. Lingas, A., Pinter, R.Y., Rivest, R.L., Shamir, A.: Minimum edge length partitioning of rectilinear polygons. In: Proc. 20th Allerton Conf. on Comm. Control and Compt., Illinos (1982)
10. Lingas, A.: Heuristics for minimum edge length rectangular partitions of rectilinear figures. In: Proc. 6th GI-Conference, Dortmund, January 1983. Springer
11. Min, M., Huang, S.C.-H., Liu, J., Shragowitz, E., Wu, W., Zhao, Y., Zhao, Y.: An Approximation Scheme for the Rectilinear Steiner Minimum Tree in Presence of Obstructions. Fields Inst. Commun. 37,155-164(2003)
12. Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: A simple new method for the geometric k-MST problem. In: Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, 1996, pp. 402-408.
13. Mitchell, J.S.B., Blum, A., Chalasani, P., Vempala, S.: A constant-factor approximation algorithm for the geometric k-MST problem in the plane. SIAM J. Comput. 28(3), 771-781 (1999)
14. Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: Part II - A simple polynomial-time approximation scheme for geometric k-MST, TSP, and related problem. SIAM J. Comput. 29(2), 515-544 (1999)
15. Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: Part III- Faster polynomial-time approximation scheme for geometric network optimization, manuscript, State University of New York, Stony Brook (1997)