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

- 53 - Простейшими среди итерационных алгоритмов являются алгоритмы парных перестановок. Рассмотрим алгоритм парных перестановок, когда в качестве критерия размещения выбрана суммарная длина межсоединений. Дано: матрица смежности С =║ С ij ║ n × n и матрица расстояний R =║ r ij ║ n × n. Пусть для определенности в качестве критерия используется суммарная длина соединений ∑ = ∑ = ∗ = n i n j p(i)p(j) ij r C F 1 1 , (6) где р ( j ) − номер позиций для j -го элемента ; р ( i ) − номер позиций для i -го эле- мента. Пусть p ( i )= h , p ( j ) = k . Переставим местами элементы e i и e j . Рассмотрим элемент е s , который с ними связан, расположенный в позиции p ( s ). Фрагмент коммутационного поля представлен на рис. 17. Найдем приращения целевой функции (6) после перестановки местами элементов е i и e j . Рис. 17 Представим выражение (6) в другом виде: D r C r C r C F s kp(s) is hk ij s hp(s) is + ∑ ∗ + ∗ + ∑ ∗ = , (7) где D - длина соединений между элементами, не затрагиваемыми перестанов- кой е i и e j . Запишем выражение (7) после перестановки e i и e j , получим новую суммарную длину : ∑ + ∗ + ∗ + ∑ ∗ = s kp(s) is hk ji s hp(s) js D r C r C r C F ~ . (8) р ( s ) ) ) k h i е i е s е