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

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

Алгоритмы и методы компоновки, размещения и трассировки радиоэлектронной аппаратуры
. Тогда задача
компоновки формулируется следующим образом, Задан мультиграф G(X,U).
Требуется “разрезать” его на отдельные куски G1(X1,U1), G2(X2,U2),…,
Gk(Xk,Uk) так, чтобы число ребер, соединяющих эти куски, было минимальным,
т.е.

минимизировать [pic] i?j

при [pic][pic] i,j = 1,2,…,k,

где Uij – множество ребер, соединяющих куски Gi(Xi,Ui) и Gj(Xj,Uj).
Другими словами разбиениями частей совокупности G на графы считаются,
если любая часть из этой совокупности не пустая; для любых двух частей
пересечение множества ребер может быть не пустым; объединение всех частей в
точности равно графу G.
Известные алгоритмы компоновки можно условно разбить на пять групп:
1. алгоритмы, использующие методы целочисленного
программирования.
2. последовательные алгоритмы
3. итерационные алгоритмы
4. смешанные алгоритмы
Алгоритмы первой группы хотя и позволяют получить точное решение
задачи, однако для устройства реальной сложности фактически не реализуемы
на ЭВМ. В последнее время наибольшее распространение получили приближенные
алгоритмы компоновки (последовательные, итерационные, смешанные). При
использовании последовательных алгоритмов сначала по определенному правилу
выбирают вершину графа, затем осуществляют последовательный выбор вершин
(из числа нераспределенных) и присоединение их к формируемому куску графа.
После образования первого куска переходят ко второму и т. д. до получения
желаемого разрезания исходного графа. В итерационных алгоритмах начальное
разрезание графа на куски выполняют произвольным образом; оптимизация
компоновки достигается парными или групповыми перестановками вершин графа
из различных кусков. Процесс перераспределения вершин заканчивают при
получении локального экстремума целевой функции, удовлетворяющим
требованиям разработчика. В смешанных алгоритмах компоновки для получения
начального варианта “разрезания” используется алгоритм последовательного
формирования кусков; дальнейшая оптимизация решения осуществляется
перераспределением вершин между отдельными кусками графа.

Последовательные алгоритмы компоновки


В последовательных алгоритмах компоновки «разрезание» исходного графа
G(X,U) на куски G1(X1,U1), G2(X2,U2),…, Gk(Xk,Uk) сводится к следующему. В
графе G(X,U) находят вершину xi [pic] X с минимальной локальной степенью
[pic].
Если таких вершин несколько, то предпочтение отдают вершине с
максимальным числом кратных ребер. Из множества вершин, смежных с вершинами
формируемого куска графа G1(X1,U1), выбирают ту, которая обеспечивает
минимальное приращение связей куска с еще нераспределенными вершинами.
Данную вершину xi [pic] X \ X1 включают в G1(X1,U1), если не происходит
нарушения ограничения по числу внешних связей куска, т.е.
[pic],
где ?j? – элемент матрицы смежности исходно графа G(X,U); ?(xg) –
относительный вес вершины xg, , равный приращению числа внешних ребер куска
G1(X1,U1) при включении вершины xg во множество X1; E – множество индексов
вершин, включенных в формируемый кусок графа на предыдущих шагах алгоритма;
m – максимально допустимое число внешних связей отдельно взятого куска со
всеми оставшимися.
Указанный процесс продолжается до тех пор, пока множество X1 не будет
содержать n элементов либо присоединение очередной нераспределенной вершины
xj к куску G1(X1,U1) не приведет к нарушению ограничения по числу внешних
соединений куска, равному
[pic]
Следует отметить, что величина [pic] не является монотонной функцией
|X1|, поэтому, для того чтобы убедится в невозможности дальнейшего
формирования куска вследствие нарушения последнего ограничения, необходимо
проверить его невыполнимость на последующих шагах увеличения множества X1
вплоть до n
10 
Добавить в Одноклассники    

 

Rambler's Top100