Рефераты Алгоритмы и методы компоновки, размещения и трассировки радиоэлектронной аппаратуры

Вернуться в Радиоэлектроника

Алгоритмы и методы компоновки, размещения и трассировки радиоэлектронной аппаратуры
.



Итерационные алгоритмы компоновки


Сущность данной группы алгоритмов заключается в выборе некоторого
начального «разрезания» исходного графа на куски (вручную или с помощью
последовательного метода компоновки) и последующего его улучшения с помощью
итерационного парного или группового обмена вершин из различных кусков. При
этом для каждой итерации осуществляется перестановка тех вершин, которая
обеспечивает максимальное уменьшение числа связей между кусками графа или
максимальное улучшение другого выбранного показателя качества с учетом
используемых ограничений (например, на максимальное число внешних ребер
любого отдельно взятого куска).
Найдем выражение для подсчета приращения числа ребер, соединяющих
куски GA(XA,UA) и GB(XB,UB), при парном обмене вершин [pic] и [pic].
Очевидно, что парная перестановка вершин xg и xh приведет к изменению
числа только тех связывающих куски GA(XA,UA) и GB(XB,UB) ребер, которые
инцидентны этим вершинам. Общее число соединительных ребер между GA(XA,UA)
и GB(XB,UB) , инцидентных xg и xh, до перестановки вершин определяют по
матрице смежности следующим образом:
[pic],
где I и J – множества индексов вершин, принадлежащих XB и XA . В этом
выражении первые два слагаемых определяют число ребер, соединяющих вершины
xg с GB(XB,UB) и xh с GA(XA,UA), а наличие третьего члена обусловлено тем,
что связь двух слагаемых учитывалась дважды.
После перестановки вершин xg и xh получим:
[pic].
Третий член выражения указывает на сохранение связи (xg, xh) после
перестановки вершин. Следовательно, в результате перестановки xg и xh
приращение числа ребер, соединяющих GA(XA,UA) и GB(XB,UB),
[pic].
Перестановка вершин целесообразна, если [pic], причем эффективность
её тем выше, чем больше [pic].
Если исходный граф G(X,U) задан матрицей смежности [pic], то
«разрезание» G(X,U) на k кусков эквивалентно разбиению матрицы A на k x k
подматриц:
[pic]

Операция парного обмена вершин xg и xh сводится к перестановке
соответствующих строк и столбцов матрицы A. Так как сумма элементов любой
подматрицы Arj определяет число ребер, связывающих Gr(Xr,Ur) и Gj(Xj,Uj),
то процесс оптимального разрезания» графа G(X,U) на куски заключается в
отыскании на каждой итерации таких парных перестановок строк и столбцов
матрицы A, при которых максимизируется сумма элементов в диагональных
подматрицах Ajj(j=1,2,…,k), что равносильно минимизации числа
соединительных ребер.
В итерационных алгоритмах предусмотрена возможность поиска
оптимального варианта для различных начальных разбиений. Это связано с тем,
что при использовании итерационных алгоритмов оптимальность решения в
значительной мере зависит от того, насколько удачно было произведено
начальное разбиение графа G(X,U).
Итерационные алгоритмы компоновки обеспечивают высокое качество
решения задачи, однако требуют больших затрат машинного времени, чем
последовательные алгоритмы. Для сокращения числа итераций обмена вершин
между кусками в смешанных алгоритмах для получения начального «разрезания»
графа применяют последовательные методы формирования его кусков. С этой
целью в некоторых итерационных алгоритмах используют процесс групповой
перестановки взаимно непересекающихся пар вершин.


3. АЛГОРИТМЫ РАЗМЕЩЕНИЯ


Исходной информацией при решении задач размещения являются: данные о
конфигурации и размерах коммутационного пространства, определяемые
требованиями установки и крепления данной сборочной единицы в аппаратуре;
количество и геометрические размеры конструктивных элементов, подлежащих
размещению; схема соединений, а также ряд ограничений на взаимное
расположение отдельных элементов, учитывающих особенности разрабатываемой
конструкции
10 
Добавить в Одноклассники    

 

Rambler's Top100