Адаптивные разбиения
Ключевые слова и синонимы
Методика построения аппроксимации
Постановка задачи
Адаптивное разбиение является одним из основных методов построения полиномиальных по времени алгоритмов аппроксимации, особенно полиномиальных схем аппроксимации для задач геометрической оптимизации. Суть метода заключается в том, что входные данные помещаются в прямоугольник, и он разбивается на меньшие прямоугольники последовательностью разрезов таким образом, что задача также разбивается на подзадачи. С каждым адаптивным разбиением можно рекурсивно построить выполнимое решение от решений в наименьших прямоугольниках к большим. С помощью динамического программирования оптимальное адаптивное разбиение вычисляется за полиномиальное время.
История вопроса
Впервые адаптивное разбиение было введено в конструкцию приближенного алгоритма Ду и др. [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]. Заметим, что guil(P) < guil(P1) + guil(P2) + a ; length(P) = length(P1) + length(P2) + length(s) ; projx(P) = projx(P1) + projx(P2):
Следовательно, guil(P) < 2- length(P) - projx(P):
Случай 2. Не существует вертикального сегмента s, длина которого больше или равна 0:5a. Выберите горизонтальный гильотинный разрез, который разбивает прямоугольник на две равные части. Обозначим за P1 и P2 обозначают две части, полученные в результате разбиения прямоугольника P. По предположению индукции, guil(Pi) < 2 ■ length(Pi) - projx(Pi) для i = 1;2. Заметим, что guil(P) = guil(P1) + guil(P2) + b ; length(P) > length(P1) + length(P2) ; projx(P) = projx(P1) = projx(P2) = b :
Следовательно, guil(P) < 2 ■ length(P) - projx(P) :
Гонсалес и Чжэн [ ] улучшили эту верхнюю границу до 1,75 и предположили, что коэффициент эффективности в данном случае равен 1,5.
Применение
В 1996 году Арора [ ] и Митчелл и др. [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)
