Случаю 2 соответствует рис. 7.38, г. Если й2 е /, мы можем преобразовать G в G, как это показано на рис. 7.38,(3, и тогда q[I. Если агф! и для соединения между 2 и Пз справедливо У аз Уа2 содержащее qi, iz, а\, az, аз поддерево не является минимальным (т. е. мы можем построить поддерево с меньшей суммарной длиной дуг). Но тогда из леммы 7.8 следует, что G не является деревом Штейнера, а это противоречит исходному предположению. В силу того что az является точкой Штейнера, она должна быть соединена по крайней мере с двумя другими вершинами, одна из которых должна лежать правее точки az на линии г/= г/. Пусть этой вершиной будет Если аз находится правее iz, то проходящая через qi вертикаль может быть передвинута подобно тому, как это показано на рис. 7.38, бив. Если же аз находится левее iz, на том же основании можно установить существование вершины находящейся справа от аз, и так далее, до тех пор пока не будет достигнута вершина а^ находящаяся правее iz- После этого вертикаль, проходящая через точку qi, может быть сдвинута, как было показано, к q[.

Рассмотрим теперь случай w{q\)> 3. В силу того что соединения проложены по прямоугольным путям, w{qi) не превосходит 4. Если qi соединена с четырьмя вершинами й, iz, аи az, то мы приходим к показанному на рис. 7.39 расположению точек. Аналогичное преобразование может быть определено и в этом случае.

Теорема 7.1. Пусть G является деревом Штейнера для множества вершин { 1, 2, п-р}, а Q - множество его -вершин. Тогда для того же множества вершин {пи 2. , Пр} существует другое дерево Штейнера с таким множеством Q его 9-вершин, что для всех q е Q справедливо е /.

Доказательство. Для доказательства достаточно последовательно применять лемму 7.13 к определенному в лемме 7.13 множеству Q до полного его исчерпания.

Из теоремы 7.1 следует, что дерево Штейнера может быть найдено путем полного рассмотрения в качестве -вершин всех возможных подмножеств точек множества / с целью определения минимального дерева покрытий для исходного множества вершин {nuHz, Пр} и -точек. Однако такой метод допустим лишь для задач с малым перебором. В настоящее время не известны эффективные процедуры поиска деревьев Штейнера для общего случая, хотя существуют процедуры для специальных классов задач. Таким образом, оказывается полезной разработка эвристических процедур построения не минимальных, а почти минимальных деревьев Штейнера. Применение таких процедур оправдано, в частности, и тем, что на практике точки.

где могут быть установлены добавочные соединения, часто не совпйдают с местоположением -точек оптимальных решений. Ниже описана эвристическая процедура, которую предложил Хенэн [12].

Процедура 7.15

1. Пусть требуется соединить множество вершин {щ, ... Пр). Разобьем вершины на классы Ро, Рь Pj в порядке

возрастания координаты х таким образом, чтобы у всех вершин одного класса была одна и та же координата х (и для Pi соответствующая л:-координата была меньше, чем для Pi + i).

2. Выбираем множество Ро вершин, имеющих наименьшую координату л;, и соединяем перпендикуляром все точки этого множества с точкой Х^ш оси х.

3. Образуем множество С, состоящее из всех точек множества /, которые были до этого соединены (необязательно непосредственно) с некоторой вершиной щ дерева, включая и сами

вершины Пг.

Рис. 7.38. К доказательству леммы 7.12, w{qi) = 3.

0 02

Рис. 7.39. К доказательству леммы 7.12, W (lyi) =4.

Рис. 7.40. Соединение (х^, с (х^, yj в процедуре 7.15.

5. Для каждой точки из Pi + i производим действия, аналогичные проделанным на предыдущем шаге, соединяя Пй с ближайшим соседом в множестве С, увеличивая, таким образом, число его элементов.

6. Повторяем шаги 4 и 5 для всех по порядку множеств Pj. Можно рассмотреть варианты этого алгоритма, в которых

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

Пример 7.18. Результаты использования процедуры 7.15 при построении минимального дерева покрытий для изображенного на рис. 7.41, G множества вершин при увеличении х, уменьшении X, увеличении у и уменьшении у представлены на рис. 7.41.

7.7.2. ТРАССИРОВКА СОЕДИНЕНИЙ

На этой стадии все элементы уже были размещены на плате, и на основании процедур, описанных в предшествующем разделе, мы приняли решение о том, какие элементы надо соединить

4. Выбираем следующее множество верщин Pj+i, имеющих наименьщую координату х. Находим точку с^С и верщину n.Pfi, такие, что d(c, tij)d[c, nj) для любых с^С и nf. е (т. е. п. - ближайший сосед текущего фрагмента графа в классе Pj+i). Соединяем точку с^, имеющую координаты [Хт, Ут), с вершиной Пу С координатами {Xi, У1) двузвен-ной ломаной линией, звенья которой параллельны координатным осям: звено, проходящее через параллельно оси х, проходящее через rij звено параллельно оси у (рис. 7.40), и включаем в множество С точку П;, а также все точки множества /, принадлежащие звену ломаной, параллельному оси у.

1 Рис. 7.41. Минимальное дерево покрытия, Z, = 20 (а); увеличение х, 1.=?= 17 (б); - уменьшение x,L=\b (в); увеличение у,1==П (г); уменьшение у, L = 17{д].

многооконечными сетями. Нам осталось теперь указать точную геометрию путей для каждого из этих соединений. Обычно при этом выдвигается такое требование, как отсутствие пересечений между соединениями; могут быть и другие ограничения, как, например, ограничение максимальной длины определенных соединений.

Во многих алгоритмах трассировки используется вариант алгоритма Ли поиска кратчайшего пути [22], основанного на программе Мура обхода лабиринта [27]. Пусть плата представлена прямоугольной сеткой, две ячейки А и А' которой должны быть соединены последовательностью горизонтальных и вертикальных отрезков. При этом возможно, что некоторые ячейки платы уже заняты (предыдущими соединениями) или по каким-либо другим причинам их использование запрещено и, следовательно, через них нельзя прокладывать путь между А и А'. Рассматриваемый алгоритм отыскивает путь между А и А', если такой путь существует, на основе построения всех допустимых путей длины 1, 2, 3, ..., k, исходящих из одной вершины, скажем вершины А, вплоть до достижения другой вершины А', или определения факта отсутствия искомого пути.

Рассмотрим изображенную на рис. 7.42, а конфигурацию, занятые (запрещенные для использования) ячейки которой заштрихованы, и попытаемся найти путь, соединяющий ячейки А и А'. На рис. 7.42, б во все незанятые, смежные с А' ячейки помещена метка 1 и таким образом показаны все возможные пути единичной длины, исходящие из А'. Этот процесс продолжен на рис. 7.42,6, где метка 2 присваивается всем ячейкам, смежным с теми ячейками, которые имеют метку 1. Вообще метка i+l присваивается ячейкам, смежным с ячейками, имеющими метку i, до тех пор, пока ячейке А не будет присвоена некоторая метка. Путь от Л' к Л определится при движении в обратном направлении по последовательности ячеек с метками k, k - I, ..., I ло достижения А'. Один из таких путей показан на рис. 7.42, е. Отметим, что путь этот не единственный. Для однозначного определения пути существует общепринятый метод, при котором в случае существования выбора направления движения не меняется без необходимости, а в случае необходимости выбирается предпочтительное направление. Если пункт назначения не был достигнут и больше нет путей, которые могут быть продолжены, работа алгоритма прекращается. К примеру, при попытке определить путь из С в С , после того как проложены соединения А-А' и В - В' (рис. 7.42, г), алгоритм закончит работу, а точка С не будет достигнута.

Для повышения эффективности алгоритма Ли было предложено несколько различных методов. На рис. 7.43, а показано, как будет работать алгоритм Ли при поиске пути из Л в Л' в

Рис. 7.42. Трассировка при помощи алгоритма Ли,

отличие от поиска пути из Л' в А. Расположение ячеек здесь то же, что и на рис. 7.42, где определялся путь из А' в А. Однако число ячеек, которые были отмечены до момента окончательного построения пути, существенно увеличилось из-за смены исходной верщины. В этом смысле рассматриваемый алгоритм будет эффективнее, если исходная верщина является ближайшей к границе.

Представляется также возможным одновременное построение путей из обеих вершин А и А' вплоть до пересечения этих путей в некоторой общей вершине. Такой подход иллюстрируется на рис. 7.43,6. При другом подходе используются искусственно создаваемые границы, окаймляющие область, внутри которой отыскивается нужный путь (рис. 7.43, в).

В описанном выше варианте алгоритма Ли для определения пути длиной k используются k различных символов. Акерз [3]

Рис. 7.43. Путь от Л к Л' (а); параллельная прокладка пути от Л к Л' (б); путь, построенный при использовании окаймления (е); метод двоичной разметки (г).

заметил, что описывающая путь последовательность символов должна удовлетворять только одному критерию, а именно: для каждого символа последовательности предшествующий символ должен отличаться от последующего, что обеспечивает возможность движения вдоль пути в обратном направлении. Он определил также, что это можно сделать, используя только два различных символа 1, 2 в последовательности 1, 1, 2, 2, 1, 1, 2, 2, .. что обеспечивает значительно большую эффективность использования памяти ЭВМ при реализации алгоритма. Такой метод построения пути из Л' в Л иллюстрируется на рис. 7.43, г.

Алгоритм Ли позволяет найти наиболее короткий путь, соединяющий две точки. Однако при этом не рассматривается вопрос успешного окончания процедуры. В этом смысле может оказаться определяющим сам порядок проведения соединений.

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

Для приведенной на рис. 7.44 схемы в случае, когда точки А и А', В и В', С и С должны быть соединены без пересечений при использовании алгоритма Ли, соединение может быть выполнено (как это показано пунктиром) только в следующем порядке: {В, В'), {А, А'), {С, С).

Для повышения вероятности успешного окончания трассировки всех соединений было предложено много различных схем определения порядка рассмотрения соединений. Наиболее простыми из них являются следующие:

1. Первым производится самое короткое соединение.

2. Первым производится самое длинное соединение.

Более сложное правило было предложено Акерзом [3]. Каждая пара соединяемых элементов {А, А') определяет прямоугольник R{A, А') на плоскости. Пусть n{R{A, А')) обозначает число точек, лежащих внутри Р(Л, Л'),которые должны быть соединены. Первыми прокладываются соединения с наименьшим значением n{R). Обоснованием этой эвристики служит той факт, что соединение между двумя ячейками (i, V) может повлиять на все последующие соединения, ведущие к ячейке /, если ячейка / лежит внутри R{i, I). Эффективность этих эвристик не была окончательно выяснена. Всестороннее исследование влияния порядка проведения соединений на успешное окончание трассировки было проведено Абелем [1].

Пример 7.19. Предположим, что необходимо провести соединения между (Л, Л'), {В, В'), (С, С), {D, D), показанной на рис. 7.45, с прямоугольной сетки. При таком расположении n{R{A, Л') = 2, n{R(B, В'))=0, n{R(C, С'))=1 и n{R{D, D)) = 2. Следовательно, согласно эвристике Акерза первое соединение, которое надо провести, - это (В, В'), затем (С, С), после чего проводятся (Л, Л') и (D, D). На рис. 7.45,6 показан возможный вариант соединений. Заметим, что эту эвристику можно усовершенствовать, пересчитывая n(R) после проведения очередного соединения и переопределяя n{R) как число еще не соединенных точек, принадлежащих R.

В некоторых случаях алгоритм Ли не обеспечивает нахождение требуемого множества соединений независимо от того, в каком порядке они проводятся. Рассмотрим схему, показанную на рис. 7.46. Пусть требуется соединить точки Л и Л', В и В', С и С, не образуя пересечений. Несмотря на то что это принципиально возможно, как показано на рисунке, алгоритм поиска

1/217 Зак, 841

i лава 7

кратчайшего пути не даст решения, вне зависимости от порядка, в котором рассматриваются соединения.

Для того чтобы алгоритм трассировки был эффективным, необходимо, чтобы он не только обеспечивал нахождение от-

Рис. 7.45. Трассировка в примере 7.19.

дельных соединений, но и обеспечивал уменьшение взаимного влияния прокладываемых соединений. Мы покажем далее, как

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

Предполагается, что плоскость, на которой размещаются элементы, состоит из множества клеток С = {сь сг, ... ..., Сп}- Каждая клетка с, является смежной для некоторого множества клеток, обозначенного Л/(с,). Если и Cj являются двумя различными элементами С, то обозначаемый через p(ci, Cj) путь из Ci в Cj является цепочкой ячеек

Сь С2, . . . , Ст, таких, что Ci = Ci, Cm =

= Cj и Ch+i e iV(Cfi) для всех k = I, m-1. Множество

всех путей из ct в с, обозначается как я(й, Cj). Поскольку некоторые пути могут быть неразрешенными (т.е. содержать запрещенные для использования ячейки), мы обозначаем через n*{Ci, Cj) множество всех разрешенных путей между Ci и Cj. Путь

Рис. 7.46. Сетка, для которой не применим алгоритм Ли.