9) Из подмножества вершин Xv с одинаковым относительным весом выбираем вершину xj с максимальной локальной степенью, т.е. .
10).
11) Если >m , то переходим к п.13.
12) Рассмотренные вершины включаем в формируемый кусок Xf = Xt .
13) Θ = Θ + 1.
14) Если Θ> α, то переходим к п.15, а противном случае – к п.7.
15) Если |Xf|<nmin, где nmin – минимально допустимое число вершин в куске, то переходим к п.21.
16) Выбираем окончательный вариант сформированного куска графа:
Xt = Xf ; X = X \ Xt ; α = nmax .
17) Если |X|> nmax , то переходим к п.20.
18) Если |X|< nmin , то переходим к п.21.
19) Определяем число внешних связей последнего куска графа:
,
где F – множество индексов вершин, входящих в X. Если , то переходим к п.21, в противном случае – к п.24.
20) Если t<k – 1 , где k - число кусков разрезания графа, то переходим к п.2, в противном случае – к п.23.
21) Предыдущий цикл «разрезания» считаем недействительным. Если t>1, т.е. имеется как минимум один ранее сформированный кусок, то переходим к п.22. в противном случае – к п.23.
22) Ищем другой допустимый вариант формирования предыдущего куска с меньшим числом вершин: t = t – 1; .
Переходим к п.7.
23) Задача при заданных ограничениях не имеет решения.
24) Конец работы алгоритма.
Рассмотренный алгоритм прост, легко реализуется на ЭВМ и позволяет получить решение задачи компоновки. Также среди достоинств данной группы алгоритмов выступает высокое быстродействие их при решении задач компоновки.
Основным недостатком последовательного алгоритма является неспособность находить глобальный минимум количества внешних связей (не анализируются возможные ситуации). Наибольшая эффективность метода последовательного разбиения графа имеет место, когда число вершин графа G значительно больше вершин в любой части разбиения.
Итерационные алгоритмы компоновки
Сущность данной группы алгоритмов заключается в выборе некоторого начального «разрезания» исходного графа на куски (вручную или с помощью последовательного метода компоновки) и последующего его улучшения с помощью итерационного парного или группового обмена вершин из различных кусков. При этом для каждой итерации осуществляется перестановка тех вершин, которая обеспечивает максимальное уменьшение числа связей между кусками графа или максимальное улучшение другого выбранного показателя качества с учетом используемых ограничений (например, на максимальное число внешних ребер любого отдельно взятого куска).
Найдем выражение для подсчета приращения числа ребер, соединяющих куски GA(XA,UA) и GB(XB,UB), при парном обмене вершин и .
Очевидно, что парная перестановка вершин xg и xh приведет к изменению числа только тех связывающих куски GA(XA,UA) и GB(XB,UB) ребер, которые инцидентны этим вершинам. Общее число соединительных ребер между GA(XA,UA) и GB(XB,UB) , инцидентных xg и xh, до перестановки вершин определяют по матрице смежности следующим образом:
,
где I и J – множества индексов вершин, принадлежащих XB и XA . В этом выражении первые два слагаемых определяют число ребер, соединяющих вершины xg с GB(XB,UB) и xh с GA(XA,UA), а наличие третьего члена обусловлено тем, что связь двух слагаемых учитывалась дважды.
После перестановки вершин xg и xh получим:
.
Третий член выражения указывает на сохранение связи (xg, xh) после перестановки вершин. Следовательно, в результате перестановки xg и xh приращение числа ребер, соединяющих GA(XA,UA) и GB(XB,UB),
.
Перестановка вершин целесообразна, если , причем эффективность её тем выше, чем больше .
Если исходный граф G(X,U) задан матрицей смежности , то «разрезание» G(X,U) на k кусков эквивалентно разбиению матрицы A на k x k подматриц:
Операция парного обмена вершин xg и xh сводится к перестановке соответствующих строк и столбцов матрицы A. Так как сумма элементов любой подматрицы Arj определяет число ребер, связывающих Gr(Xr,Ur) и Gj(Xj,Uj), то процесс оптимального разрезания» графа G(X,U) на куски заключается в отыскании на каждой итерации таких парных перестановок строк и столбцов матрицы A, при которых максимизируется сумма элементов в диагональных подматрицах Ajj(j=1,2,…,k), что равносильно минимизации числа соединительных ребер.
В итерационных алгоритмах предусмотрена возможность поиска оптимального варианта для различных начальных разбиений. Это связано с тем, что при использовании итерационных алгоритмов оптимальность решения в значительной мере зависит от того, насколько удачно было произведено начальное разбиение графа G(X,U).
Итерационные алгоритмы компоновки обеспечивают высокое качество решения задачи, однако требуют больших затрат машинного времени, чем последовательные алгоритмы. Для сокращения числа итераций обмена вершин между кусками в смешанных алгоритмах для получения начального «разрезания» графа применяют последовательные методы формирования его кусков. С этой целью в некоторых итерационных алгоритмах используют процесс групповой перестановки взаимно непересекающихся пар вершин.
3. АЛГОРИТМЫ РАЗМЕЩЕНИЯ
Исходной информацией при решении задач размещения являются: данные о конфигурации и размерах коммутационного пространства, определяемые требованиями установки и крепления данной сборочной единицы в аппаратуре; количество и геометрические размеры конструктивных элементов, подлежащих размещению; схема соединений, а также ряд ограничений на взаимное расположение отдельных элементов, учитывающих особенности разрабатываемой конструкции. Задача сводится к отысканию для каждого размещаемого элемента таких позиций, при которых оптимизируется выбранный показатель качества и обеспечивается наиболее благоприятные условия для последующего электрического монтажа. Особое значение эта задача приобретает при проектировании аппаратуры на печатных платах.
Основная сложность в постановке задач размещения заключается в выборе целевой функции. Связано это с тем, что одной из главных целей размещения является создание наилучших условий для дальнейшей трассировки соединений, что невозможно проверить без проведения самой трассировки. Любые другие способы оценки качества размещения (минимум числа пересечений ребер графа, интерпретирующего электрическую схему соединений, разбиение графа на минимальное число плоских суграфов и т.д.), хотя и позволяют создать благоприятные для трассировки условия, но не гарантируют получение оптимального результата, поскольку печатные проводники представляют собой криволинейные отрезки конечной ширины, конфигурация которых определяется в процессе их построения и зависит от порядка проведения соединений. Следовательно, если для оценки качества размещения элементов выбрать критерий, непосредственно связанный с получением оптимального рисунка металлизации печатной платы, то конечный результат может быть найден только при совместном решении задач размещения, выбора очередности проведения соединений и трассировки, что практически невозможно вследствие огромных затрат машинного времени.
Поэтому все применяемые в настоящее время алгоритмы размещения используют промежуточные критерии, которые лишь качественно способствуют решению основной задачи: получению оптимальной трассировки соединений. К таким критериям относятся: 1) минимум суммарной взвешенной длины соединений; 2) минимум числа соединений, длина которых больше заданной; 3) минимум числа пересечение проводников; 4) максимальное число соединений между элементами, находящимися в соседних позициях либо в позициях, указанных разработчиком; 5) максимум числа цепей простой конфигурации.
Наибольшее распространение в алгоритмах размещения получил первый критерий, что объясняется следующими причинами: уменьшение длин соединений улучшает электрические характеристики устройства, упрощает трассировку печатных плат; кроме того, он сравнительно прост в реализации.
В зависимости от конструкции коммутационной платы и способов выполнения соединений расстояние между позициями установки элементов подсчитывается по одной из следующих формул:
, ,
В общем виде задача размещения конструктивных элементов на коммутационной плате формулируется следующим образом. Задано множество конструктивных элементов R={r1,r2,…,rn} и множество связей между этими элементами V={v1,v2,…,vp}, а также множество установочных мест (позиций) на коммутационной плате T={t1,t2,…,tk}. Найти такое отображение множества R на множестве T, которое обеспечивает экстремум целевой функции
, где cij – коэффициент взвешенной связности.
Силовые алгоритмы размещения
В основу этой группы алгоритмов положен динамический метод В.С. Линского. Процесс размещения элементов на плате представляется как движение к состоянию равновесия системы материальных точек (элементов), на каждую из которых действуют силы притяжения и отталкивания, интерпретирующие связи между размещаемыми элементами. Если силы притяжения, действующие между любыми двумя материальными точками ri и rj пропорциональны числу электрических связей между данными конструктивными элементами, то состояние равновесия такой системы соответствует минимуму суммарной длины всех соединений. Введение сил отталкивания материальных точек друг от друга и от границ платы исключает возможность слияния двух любых точек и способствует их равномерному распределению по поверхности монтажного поля. Чтобы устранить возникновение в системе незатухающих колебаний, вводят силы сопротивления среды, пропорциональные скорости движения материальных точек.
