Алгоритм Рабина

Увеличение быстродействия в алгоритме Рабина достигается за счёт преимущественного распространения волны в направлении ячейки-цели.

В алгоритме Ли, который является реализацией метода динамического программирования, такая целенаправленность отсутствует.

Алгоритм Рабина, который реализует метод ветвей и границ, позволяет также, как и алгоритм Ли, находить глобальный оптимум целевой функции (L_min).

Пусть требуется найти путь min длины между ячейками А и В.

Рассмотрим некоторую ячейку С_i , включаемую в очередной фронт волны. Значение волновой функции С_i , приписываемое С_i ячейки фронта, определяется из выражения:

,

где L(I,A) – длина пройденного волной пути из ячейки А в ячейку С_i , а

- расстояние между С_i,В в ортогональной метрике.

Нетрудно увидеть, что является нижней оценкой пути из С_i в В, полученной в предположении отсутствия препятствий на этом пути.

Отсюда, выражение (1) в целом представляет собой нижнюю оценку пути из А в В, проходящую в ячейку С_i .

Согласно методу ветвей и границ, оптимальное решение следует искать в подмножестве решений, имеющем наилучшую оценку. В соответствии с этим в сформированном очередном фронте волны выделяют подмножество ячеек с min оценкой 1 и распространение волны на следующем шаге осуществляется из ячеек этого подмножества.

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

Последовательность просмотра соседних ячеек та же, что и в алгоритме Ли (например:,,,) - построение пути осуществляется с использованием путевых координат.

Эффективность алгоритма Рабина по сравнению с алгоритмом Ли показана на рис.3, на котором для каждой ячейки ДПР указано значение весовой функции P_i. Цифрами в правых углах ячеек обозначена последовательность рассмотрения ячеек на этапе распространения волны.

рисунок

Алгоритм слежения за целью.

Возможно дальнейшее сокращение зоны поиска при трассировке в случае приближений реализации метода ветвей и границ, получивших название «алгоритм слежения за целью». В этом алгоритме в качестве значений весовой функции для ячейки С_i на этапе распространения волны используется выражение (2).

Здесь распространение волны происходит из тех ячеек очередного фронта, которые ближе расположены к ячейке – зоне (запрещённые ячейки не учитываем). При этом сокращается зона поиска. Однако, из-за приближённого вычисления нижней оценки для подмножества путей, ведущих из А в В через С-пути, возможна потеря глобального минимума.

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

Примечание. В этом алгоритме распространение волны осуществляется от множества ячеек с минимальной оценкой, начиная с ячейки, которая получила эту минимальную оценку последней (или первой).

Пример: поле 12*8.

рисунок

Распределение соединений по слоям многослойной печатной платы.

Многослойный монтаж печатных (плёночных) соединений между компонентами электронной схемы позволяют сократить суммарную длину соединений (τ_{зад. min}), уменьшить вес и габариты проектируемой аппаратуры.

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

Целью решения этой задачи является обеспечение 100% трассировки соединений, уменьшение числа слоёв и межслойных переходов, наиболее рациональное использование объёма монтажного пространства.

Алгоритмическое распределение соединений по слоям может выполняться до, после или в процессе трассировки отдельных соединений.

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

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

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

Большинство приближенных алгоритмов расслоения до трассировки связана с введением определенных количественных оценок, конфликтуемости цепей при их распределении в 1 слой. Эти оценки вычисляются на основе инф-ии о расположении элементов и контактов цепей, полученных после решения задач размещения. Такого рода оценки могут зависеть от степени перекрытия минимальных прямоугольников, охватывающих контакты отдельных цепей, числа контактов цепей и т.д. После определения степени конфликтуемости каждой пары цепей строится взвешенный неор. граф конфликтов, в котором кажд.вершине h€H соответствует некоторая цепь, а каждому ребру v_i,j €V соот-т наличие конфликта между цепями Hi и Hj.Вес принимается равным оценке конфликтуемости между соот-ми цепями. Далее осуществляется раскраска вершин графа G в заданное число цветов, при котором сумма весов ребер, соединяющих вершин одного цвета минимальна. Раскраска вершин графа конфликтов осуществляется различными эвристическими алгоритмами.

Расслоение после предварительной трассировки состоит в следующим. На 1-м этапе с помощью одного из алгоритмов построения кратчайших, связ-х деревьев(КСД) осуществляется предварительная трассировка соединений в одном слое. В процессе получения совмещенной топологии минимизируется такие геометрические размеры как длина, число перегибов, число пересечений. Далее также, как и в алгоритме расслоения до трассировки строится граф конфликтов, но не между цепями, а между отдельными двухконтактными соединениями(отрезками проводников) При этом граф конфликтов G=(X,V) явл-ся неорг-м графом, наличие ребра в котором между x_i и y_j соответствует пересечению отрезков в совмещенной топологии.

Пример

К=2(требуемое число слоев)

Вершина ГК раскрашивается в заданное минимальное число цветов так, что вершина первого цвета не имеет ни 1 единого ребра. Каждое подмножество, соответ-е вершинам 1-го цвета распределяется в 1 из слоев. Не вошедшие ни в 1 из подмножеств отрезки,(что м. иметь место при заданном К последовательно распределяется в те слои, в которых они имеют минимальное число пресечений).

Расслоение в процессе трассировки осуществляется одновременно с прокладкой соединений многослойным ДРП с помощью различных модификаций волнового алгоритма трассировки. Рассмотрим математическую постановку задачи по слоям после предварительной трассировки. Будем считать число слоев К. Пусть G=(X,Y)– граф пересечений, в котором каждой вершинеx_i соответствует отрезок i, i=1,n, а ребру(x_ix_j)соответствует n отрезков i и j в совмещенной топологии.

Требуется распределить отрезки по слоям, т.о., чтобы суммарное число пересечений было минимальным.

Введем в рассмотрение матрицу Y=[y_ij]_n*k 1, отр-к x_i помещен в слой j

y_ij= 0, в противном случае

При таком подходе задача расслоения может быть сформулирована:

Требуется минимизировать (*), где c_ij – соответствующий элемент матрицы смежности c_ij = 1, если i и p конфл-т между собой

0, в прот. Случае

На элементы i и j наложены ограничения:

(любой отрезок может быть помещен в 1 из слоев)

Данная задача является квадратичной задачей целочисленного программирования с булевыми переменными (y_ij,y_pj) Рассмотрим приближенный алгоритм ее решения.

Алгоритм расслоении МПП

1. В соответствие с результатами предварительной трассировки строится граф конфликтов отрезков в размещенной топологии схемы.

2. Из графа конфликтов последовательно удаляется вершины, имеющие локальную степень(число ребер, инцидентных вершине)<K. Удаление вершин здесь и далее осуществляется вместе с инцидентными им ребрами. Формируется список таких вершин. Очевидно, что отрезки, соот-ие таким вершинам может быть реализованы в слоях К без пересечений.

3. Формируется список S1 отрезков, распределенных в 1-й слой. С этой целью в графе G1=(X1,V1), гдеX1=XS; V1=VVs, гдеVs – множество ребер, инцидентных вершинам множества S. В этом графе находится максимальное число несмежных между собой вершин. При этом используется приближенная процедура. Из графа G1 последовательно удаляется вершины с максимальными локальными степенями до получения графа без ребер. Множество оставшихся при этом вершин графа включается в список S1. Очевидно, что соответствующие этому списку отрезки между собой не конфликтуют и могут быть расположены в 1-м слое без пересечений

4. Далее из графа G1, из которого исключены вершины списка S1 последовательно удаляются и заносятся в список S вершины, имеющие локальную степень <(K-1). Отрезки, соответ-ие этим вершинам всегда м.б. расположены в (К-1) слой (кроме 1-го) без пересечений. Получаем граф G2=(X2,V2) X2=X(SUS1); V2=(VsUVs1)

5. Аналогично формируются S1S2,S3,..,Sk. При этом м. остаться некоторое множество отрезков S*, которое нельзя реализовать без пересечений в 1-м слое.

6. Из списка S последовательно в порядке, обратно порядку включения в список выбирается очередной отрезок и включается в тот слой, в который он не имеет пересечений. Так слой найдется, что следует из процедуры формирования списка S.

7. Из списка S* последовательно выбирается очередной отрезок и распределяется в тот слой, где имеет минимальной число n. Если слоев несколько, то отрезок распределяется в слой с меньшим общим числом отрезков.

Пример: Пусть К=3. Граф конфликтов:

Последовательно удаляем вершины локальной степени, кот.<3. Формируем S={2,6,1,4,3,5,7} Строим G1=(X1,V1). Представим на рисунке

Из графа G1 последовательно удаляем вершины с максимальной локальной степенью. Сначала исключается вершина 11, затем 12,13,9,8,10. Вершина списка S1={14,15} – образуют внутреннее устойчивое множество, т.е. максимальное несмежной между собой число вершин (п.3). Из графа G1 удаляется вершина S1; получаем

Список S здесь не дополняется, т.к. отсутствуют вершины локальной степени, которые <(K-1)=2 (п.4)

Из графа G2 последовательно удаляется вершины с максимальной локальной степенью (11,9,8,10) и получаем S2={12,13}. Назначаем им 2-й слой. Строим G3(без 12 и 13). Из G3 находим S3={8,10}, которое распределяем в 3-й слой.

Т.о. S1={14,15,7,5,6,3,11}

S2={12,13,4,2,} S3={8,10,1,9}

Трассировка проводного монтажа (провода с изоляцией)

Т.М. м. осуществляться по прямым, соединяющим выводы эл-ты (монтаж в навал) или с помощью жгутов, к-е прокладывается в специальных каналах. Ограничения: количество проводников, к-е можно подсоединить к 1 выводу и число проводов в каждом жгуте – пропускная способность каналов.

Т.П.М, заключается в определении порядка соединения выводов в соответствии со схемой или с учетом ограничений. Критерий качества – минимальной суммарной длиной проводников. Нахождение порядка соединения выводов модулей внутри цепи сводится к задаче нахождения КСД.

Будем использовать модель схемы(цепи) в виде графа, в к-м выводов элементов сопоставлены вершины и на этой вершине строится полный граф цепи. Число вершин графа = n, при этом число ребер полного графа r=n(n-1)2

При таком подходе каждая цепь представляется отдельной компонентой связности.

Ставится задача построения КСД на тех комп-х связности число вершин которых>2.

Отметим, что на n вершинах полного графа можно построить tn деревьев.

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

Алгоритм Красккала

Пусть задан G=(X,V) i,j=1,n, i≠j

Каждому ребру Vij поставлено в соответствие число Cij – вес или длина данного ребра.

Ставится задача: среди всех деревьев (n-(n-2)), кот. м. выделить в данном графе, требуется найти дерево с минимальной длиной в дереве (n-1) ребро.

Пусть C=[c_ij]_n*n матрица длины ребер графа.

1. Все ребра графа n(n-1)2 упорядочива-ся п порядке убывания длины, начиная с ребра C1=min_i,jCij

……

Cn=max_i,jCij

1. Последовательно просматривается рассматриваемое множество V* длин ребер на каждом шаге, включенным в дерево одно ребро. В качестве такого ребра выбирается ребро среди не включенных в дерево, имеющих минимальную длину и не образующих циклов с ребрами уже вошедших в дерево.
2. Отметим: при работе этого алгоритма возможно появление несвязных поддеревьев, которое затем соединяется, образуя одну компоненту связности.

Лекция 12

Требуется построить КСД для цепи содержащей 6 контактов. Полный граф на рис:

Пусть матрица длин ребер графа цепи имеет вид:

U= n = 6; n*(n-1) = 15

рис.1

1. Упорядочивание длин ребер полного графа

- 15 элементов.

2.1. Включаем в в дерево получаем 1-ую изолир-ую компоненту связности.

2.2. Включаем в дерево , получаем 2-ую изолир. компоненту связности (2,3).

2.3. Включаем - получаем 3-ю изолир. компоненту связности (4,5).

2.4. Включ. - получаем 4-ю изолир. компоненту связности (1,6,4,5).

Ребро образовывает цикл - брать нельзя.

Ребро тоже образовывает цикл - брать нельзя.

2.5. Вкл-м в дерево . КСД построено.

Примечание: цикл образ-я тогда, когда обе вершины включаемого ребра ываываыавыавы

Недостатки:

1) Необходимо на каждом шаге проверять условия необраз-я цикла, а так же наблюд-е за различными компонентами связности.

2) Большое время уходит на упорядочивание ребер полного графа.

Дата добавления: 2014-01-14