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

  • Просмотров 9531
  • Скачиваний 377
  • Размер файла 64
    Кб

ограничения на число внешних связей и входящих в него вершин (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) = 5)     Из подмножества вершин Xl с одинаковой локальной степенью выбирают вершину xj с максимальным числом кратных ребер (минимальным числом смежных вершин), т.е. |Гxj| = 6)     Запоминаем исходную вершину формируемого куска графа 7)     По матрице смежности строим множество Xs = и определяем относительные веса вершин . 8)     Из множества XS выбираем вершину п.10. Если таких

вершин несколько, то переходим к п.9. 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. Если 20) Если t<k – 1 , где k - число кусков разрезания графа, то переходим к п.2, в противном случае – к п.23. 21) Предыдущий цикл «разрезания» считаем недействительным. Если t>1, т.е. имеется

как минимум один ранее сформированный кусок, то переходим к п.22. в противном случае – к п.23. 22) Ищем другой допустимый вариант формирования предыдущего куска с меньшим числом вершин: t = t – 1; Переходим к п.7. 23) Задача при заданных ограничениях не имеет решения. 24) Конец работы алгоритма. Рассмотренный алгоритм прост, легко реализуется на ЭВМ и позволяет получить решение задачи компоновки. Также среди достоинств данной группы