7.1.6. Задача Штейнера

Виды используемых деревьев определяются технологией выполнения соединений и схемотехническими требованиями. При автоматизированном конструировании схем проводного и печатного монтажа ставятся разные задачи построения минимальных деревьев соединений. В первом случае не допускается вводить дополнительные вершины (соединение «контакт» - «контакт»). Для решения такой задачи используют рассмотренные ранее эффективные алгоритмы Краскала, Прима и другие. Во втором случае разрешается вводить дополнительные вершины и соединяющие их ребра (соединения «контакт» - «проводник», «проводник» - «проводник»). Такая задача называется задачей Штейнера (J. ), деревья соединений – деревьями Штейнера (ДШ), а дополнительные вершины – точками Штейнера (ТШ).

Задача построения дерева Штейнера имеет следующий вид. Требуется найти такой связный ациклический граф с использованием дополнительных вершин Штейнера (дерево Штейнера) Т’ = (Х’,U’), что Х’ включает все вершины Х и дополнительные вершины (вершины Штейнера) и суммарный вес ребер в T’ будет минимальным. На рис. 7.14 (а) показано МСД, суммарная длина ребер - 10,123, а на рис. 7.14 (б) – дерево Штейнера, суммарная длина ребер – 9,196.

а

б

Рисунок 7.14. МСД (а) и дерево Штейнера (б)

Задача о соединении точек оптимальным образом – одна из старейших оптимизационных задач. Она восходит еще к П. Ферма (Pierre de Fermat). Еще в ХVII столетии была предложена следующая задача. На плоскости найти такую точку Р, которая минимизирует суммарное расстояние от Р до трех заданных точек плоскости. Ферма, Торричелли (E. Torricelli) и Кавальери (B.F. Cavalieri) независимо друг от друга нашли решение этой задачи.

Общим решением этой задачи является следующее. Точка Р либо лежит внутри треугольника, построенного на заданных точках, либо совпадает с одной из этих точек. В первом случае каждый из углов между отрезками, соединяющими Р с каждой их точек, составляет 120⁰. Во втором случае угол, образованный отрезками, соединяющими эту точку с другими заданными точками, равен или больше 120⁰. Рис. 7.15. демонстрирует способ решения задачи, найденный в середине ХVII века.

Для отыскания точки Р, ближайшей (в смысле суммарного расстояния) к заданным точкам А, B, C, сначала строится треугольник (АBC) и на одной из его сторон, например на АC, строится равносторонний треугольник. (АBХ) так, что точка В лежит вне этого треугольника. Точка пересечения окружности, описанной вокруг равностороннего треугольника (АBХ), с отрезком (BХ) есть искомая точка Р.

Т

B

очкой Торричелли треугольника (ABC) называется такая точка Р, из которой стороны данного треугольника видны под углом 120⁰, т.е. углы AРB, AРC и BРC равны 120⁰.

C

P

A

x

Рисунок 7.15. Нахождение точки Торричелли

Трехточечная задача используется как составная часть алгоритмов решения задачи Штейнера.

Перебираем тройки вершин графа и находим точки Торричелли. Выбираем такие точки, включение которых в дерево даст максимальный эффект.

Задача Штейнера относится к классу так называемых NP-полных задач, поэтому алгоритмы, дающие точные решения, как правило, не могут быть использованы в САПР из-за неприемлемой временной сложности. Это обстоятельство послужило стимулом для разработки многочисленных эвристических алгоритмов. Наибольший практический интерес представляет алгоритм последовательного введения дополнительных вершин в дерево Прима-Краскала.

Возможно, наиболее важным практическим применением задачи Штейнера является конструирование интегральных электронных схем. Более короткая сеть проводящих линий на интегральной схеме требует меньшего времени зарядки-разрядки по сравнению с более длинной сетью и повышает, таким образом, быстродействие схемы. Однако задача отыскания кратчайшей сети на интегральной схеме имеет другую геометрию, так как проводники на ней обычно проходят лишь в двух направлениях — горизонтальном и вертикальном. Такая задача получила название прямоугольной задачи Штейнера.

Для случая ортогональной метрики доказано, что если через каждую точку из исходного множества точек провести горизонтальные и вертикальные линии, то решение задачи Штейнера можно получить, рассматривая в качестве возможных дополнительных вершин только точки пересечения полученной сетки линий (рис.7.16 (а)).

Алгоритм последовательно вводит в текущее дерево Прима-Краскала каждую из дополнительных вершин решеточного графа, строит новое дерево Прима и запоминает полученный выигрыш в длине. После оценки всех дополнительных точек в текущее дерево включается точка с максимальным выигрышем (рис.7.16 (б)). При этом, чтобы избежать в процессе преобразования появления избыточных точек, необходимо учитывать, что дополнительные точки в дереве Штейнера могут иметь только степень 3 и 4.

Рисунок 7.16. Кратчайшие остовное дерево (а) (L = 18)

и дерево Штейнера (б) (L = 15)

Рассмотрим некоторые эвристические методы построения деревьев Штейнера.

Метод Ханана

Метод Ханана (M. Hanan) заключается с следующем.

1. Все множество вершин с координатами s разбивается на классы S₁, S₂, ..., S_m в порядке неубывания координаты s_i так, чтобы у всех вершин одного класса была одинаковая координата s.

2. Анализируется множество вершин класса S₁ и соединяется между собой прямой.

3. Образуется множество I, состоящее из вершин, включенных в дерево и точек, принадлежащих построенной прямой.

4. Выбирается следующее множество S_i+1, имеющее наименьшую координату s. Для вершины x_k S_i+1 определяется точка x_j, для которой d_kj = min{d_kg} x_gI. Вершина x_k соединяется двухзвенной ломаной линией с точкой x_jI.

5. Для очередной вершины класса S_i+1 операция подсоединения к дереву выполняется в соответствии с пунктами 3, 4.

6. Пункты 3, 4, 5 повторяются для всех множеств S_i до построения полного дерева.

Рассмотрим пример построения дерева Штейнера по методу Ханана для вершин, представленных на рис. 7.17 (а).

1. Разобьем множество вершин X = {x₁, x₂, ..., x₅} на классы по неубыванию координаты s_i, получим: S₁={x₁}, S₂={x_2, x₃}, S₃={x₄}, S₄={x₅}.

2. В классе S₁ всего одна вершина, поэтому соединение вершин не производим.

3. Вершину x₂S₂ соединяем с x₁ двухзвенной ломаной линией, причем сначала в направлении перпендикулярном оси s, а затем оси t.

4. Вершину x₃ S₂ соединяем с ближайшей точкой уже построенного фрагмента.

5. Переходим в следующий класс и x₄ S₃ соединяем с ближайшей точкой дерева, получаем ТШ 1.

6. Вершину x₅ S₄ соединяем по кратчайшему расстоянию с ближайшей точкой построенного дерева, получаем ТШ 2.

Р езультат построения дерева Штейнера с суммарной длиной ребер L=11 представлен на рис. 7.17 (б).

Рисунок 7.17. Вершины графа (а); дерево Штейнера (метод Ханана) (б)

Столб Штейнера

Метод "Столб Штейнера" является одним из наиболее эффективных по времени реализации эвристических алгоритмов построения дерева Штейнера и предусматривает следующий порядок действия.

1. Все вершины проецируются на ось s.

2. Расстояние от наименьшей до наибольшей координаты s делится пополам, и из этой точки проводится перпендикуляр (столб Штейнера).

3. Из каждой вершины опускается перпендикуляр до пересечения со столбом Штейнера.

Рассмотрим пример построения дерева Штейнера по данному методу для представленного на рис. 7.17 (а) множества вершин.

1. Находим среди множества проекций на ось s (s₁=1, s₂= s₃=2, s₄=4, s₅=5) минимальное и максимальное значения: mins_i = s₁ = 1, maxs_i = s₅ = 5.

2. Вычисляем координату проведения столба Штейнера: s_i = (s₁ + s₅) / 2 = 3.

3. Проводим столб Штейнера с координатой s_i = 3 и опускаем из всех вершин перпендикуляры до пересечения со столбом.

Результат построения дерева Штейнера с суммарной длиной ребер L=12 представлен на рис. 7.18 (а).

Аналогично строится горизонтальный столб (рис. 7.18 (б)), L=12.

Рисунок 7.18. Деревья Штейнера, построенные методом "Столб Штейнера", (

а) – вертикальный; (б) – горизонтальный столбы

Временная сложность алгоритма О(n²).

В. На втором этапе предпринимается попытка точно решить, на каком слое каждое соединение может располагаться.

Расслоение можно проводить до, после или во время трассировки отдельных соединений. Расслоение основано на анализе схемы соединений для выявления конфликтующих проводников.

Если расслоение проводится до собственно трассировки, то для контактов каждой цепи строится минимальный охватывающий прямоугольник. Строится граф перекрытий прямоугольников, вершины которого цепи, а ребра между вершинами проводятся, если прямоугольники перекрываются. Граф перекрытий раскрашивается в минимальное число цветов. В результате: цвет – слой.

Если расслоение проводится после трассировки, то получают совмещенную топологию. Строят граф пересечений, в котором вершины – проводники, а ребра их соединяют, если проводники пересекаются. Граф пересечений раскрашивается в минимальное число цветов.

Расслоение в процессе трассировки будет рассмотрено в подразделе 7.4.7.