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

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

Алгоритмы и методы компоновки, размещения и трассировки радиоэлектронной аппаратуры
. В качестве окончательного варианта выбирают кусок
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 для сокращения
объема оперативной памяти ЭВМ используем не саму матрицу смежности,
а её кодовую реализацию), определяем локальные степени вершин
[pic].
4) Из множества нераспределенных вершин X выбираем вершину xj с ?(xj)
= [pic]. Переходим к п.6. Если таких вершин несколько, то переходим
к п.5
5) Из подмножества вершин Xl с одинаковой локальной степенью выбирают
вершину xj с максимальным числом кратных ребер (минимальным числом
смежных вершин), т.е. |Гxj| = [pic].
6) Запоминаем исходную вершину формируемого куска графа [pic].
Переходим к п.10
7) По матрице смежности [pic] строим множество Xs = [pic] и определяем
относительные веса вершин [pic]:
[pic].
8) Из множества XS выбираем вершину [pic]. Переходим к п.10. Если
таких вершин несколько, то переходим к п.9.
9) Из подмножества вершин Xv с одинаковым относительным весом выбираем
вершину xj с максимальной локальной степенью, т.е. [pic].
10) [pic].
11) Если [pic]>m , то переходим к п.13.
12) Рассмотренные вершины включаем в формируемый кусок Xf = Xt .
13) ? = ? + 1.
14) Если ?> ?, то переходим к п.15, а противном случае – к п.7.
15) Если |Xf| куске, то переходим к п.21.
16) Выбираем окончательный вариант сформированного куска графа:
Xt = Xf ; X = X \ Xt ; ? = nmax .
17) Если |X|> nmax , то переходим к п.20.
18) Если |X|< nmin , то переходим к п.21.
19) Определяем число внешних связей последнего куска графа:
[pic],
где F – множество индексов вершин, входящих в X. Если [pic],
то переходим к п.21, в противном случае – к п.24.
20) Если t переходим к п.2, в противном случае – к п.23.
21) Предыдущий цикл «разрезания» считаем недействительным. Если t>1,
т.е. имеется как минимум один ранее сформированный кусок, то
переходим к п.22. в противном случае – к п.23.
22) Ищем другой допустимый вариант формирования предыдущего куска с
меньшим числом вершин: t = t – 1; [pic].
Переходим к п.7.
23) Задача при заданных ограничениях не имеет решения.
24) Конец работы алгоритма.

Рассмотренный алгоритм прост, легко реализуется на ЭВМ и позволяет
получить решение задачи компоновки. Также среди достоинств данной группы
алгоритмов выступает высокое быстродействие их при решении задач
компоновки.
Основным недостатком последовательного алгоритма является
неспособность находить глобальный минимум количества внешних связей (не
анализируются возможные ситуации). Наибольшая эффективность метода
последовательного разбиения графа имеет место, когда число вершин графа G
значительно больше вершин в любой части разбиения
10 
Добавить в Одноклассники    

 

Rambler's Top100