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

Страница: 2/8

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

В последовательных алгоритмах компоновки «разрезание» исходного графа G(X,U) на куски G1(X1,U1), G2(X2,U2),…, Gk(Xk,Uk) сводится к следующему. В графе G(X,U) находят вершину xi X с минимальной локальной степенью .

Если таких вершин несколько, то предпочтение отдают вершине с максимальным числом кратных ребер. Из множества вершин, смежных с вершинами формируемого куска графа G1(X1,U1), выбирают ту, которая обеспечивает минимальное приращение связей куска с еще нераспределенными вершинами. Данную вершину xi X X1 включают в G1(X1,U1), если не происходит нарушения ограничения по числу внешних связей куска, т.е.

,

где αjε – элемент матрицы смежности исходно графа G(X,U); δ(xg) – относительный вес вершины xg, , равный приращению числа внешних ребер куска G1(X1,U1) при включении вершины xg во множество X1; E – множество индексов вершин, включенных в формируемый кусок графа на предыдущих шагах алгоритма; m – максимально допустимое число внешних связей отдельно взятого куска со всеми оставшимися.

Указанный процесс продолжается до тех пор, пока множество X1 не будет содержать n элементов либо присоединение очередной нераспределенной вершины xj к куску G1(X1,U1) не приведет к нарушению ограничения по числу внешних соединений куска, равному

Следует отметить, что величина не является монотонной функцией |X1|, поэтому, для того чтобы убедится в невозможности дальнейшего формирования куска вследствие нарушения последнего ограничения, необходимо проверить его невыполнимость на последующих шагах увеличения множества X1 вплоть до n. В качестве окончательного варианта выбирают кусок G10(X10,U10), содержащий максимально возможное число вершин графа G(X,U), для которого выполняются ограничения на число внешних связей и входящих в него вершин (nmin-nmax).

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

Сформулируем алгоритм последовательной компоновки конструктивных элементов.

1) t:0

2) Xf = Xt = Ø; t=t+1; Θ=1; α=nmax,

Где t, Θ – порядковые номера формируемого куска и присоединяемой вершины; α – ограничение на число вершин в куске.

3) По матрице смежности исходного графа | αhp|NxN, где N – число вершин исходного графа (при большом значении N для сокращения объема оперативной памяти ЭВМ используем не саму матрицу смежности, а её кодовую реализацию), определяем локальные степени вершин .

4) Из множества нераспределенных вершин X выбираем вершину xj с ρ(xj) = . Переходим к п.6. Если таких вершин несколько, то переходим к п.5

5) Из подмножества вершин Xl с одинаковой локальной степенью выбирают вершину xj с максимальным числом кратных ребер (минимальным числом смежных вершин), т.е. |Гxj| = .

6) Запоминаем исходную вершину формируемого куска графа . Переходим к п.10

7) По матрице смежности строим множество Xs = и определяем относительные веса вершин :

.

8) Из множества XS выбираем вершину . Переходим к п.10. Если таких вершин несколько, то переходим к п.9.

9) Из подмножества вершин Xv с одинаковым относительным весом выбираем вершину xj с максимальной локальной степенью, т.е. .

Реферат опубликован: 16/12/2006