Информационные технологии проектирования электронных средств

- 54 - Определим приращение ∆ ∑ ≠ ∑ = ∗ − − ∗ − = − = i,j s s s kp(s) js is hp(s) js is ij r )C (C r )C (C FF F ~ ∑ − ∗ − = s kp(s) hp(s) js is ) r (r )C (C . Алгоритмы парных перестановок отличаются стратегией выбора пары элементов. Рассмотрим одну из них. Все элементы упорядочим в соответствии с убыванием характеристики ∑ = = n j ij i C C 1 )1 ( ,n i = . Таким образом находим последовательность номеров элементов на оче- редной итерации : I = i 1 , i 2 ,…, i n ( C i 1 ≥ C i 2 ≥ … ≥ C in ). Затем для каждого элемента рассчитывается приращение ∆ F ij при усло- вии, что очередной элемент переставляется с элементом, стоящим правее его в последовательности I . Далее из всех значений ∆ jνi F >0 мы выбираем наиболь- шее положительное и переставляем местами элементы νie и e j . Если для неко- торого элемента νie не окажется приращения ∆ jνi F >0, то этот элемент останется на месте. Рассмотрим алгоритм парных перестановок , когда в качестве критерия размещения выбрана максимальная длина межсоединений. При решении задачи размещения могут появиться связи, длина которых превышает критическую. Максимальная длина соединений в схеме непосредственно определяет задержку при распространении электрических сигналов. Введем матрицу nn ij b B × = , в которой     = = ≠ = , с , b , c , b ij ij ij ij 0 если 0 0 если 1