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

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

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

перестановками вершин графа из различных кусков. Процесс перераспределения вершин заканчивают при получении локального экстремума целевой функции, удовлетворяющим требованиям разработчика. В смешанных алгоритмах компоновки для получения начального варианта “разрезания” используется алгоритм последовательного формирования кусков; дальнейшая оптимизация решения осуществляется перераспределением вершин между

отдельными кусками графа. Последовательные алгоритмы компоновки     В последовательных алгоритмах компоновки «разрезание» исходного графа 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), для которого выполняются