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

- 50 - Найдем )a, (a max j i ji, , который даст нам значение либо строки i o (номер элемента), либо столбца j o (номер установочного места). Если мы определим i o, , то j0i j0i amin a j 0 = . Если мы определили номер столбца j o , то 0ij i 0j0i amin a = . Индекс i o дает номер элемента, который подлежит размещению в позицию S j 0 . Цена назначения а ij пересчитывается на каждом шаге работы алгоритма размещения. Она определяется как приращение целевой функции при установ- ке каждого неразмещенного элемента e i ∈ к Е в незанятую позицию s j ∈ S к . Метод обратного размещения Предварительно оценивается каждый из элементов e 1 , e 2 ,…, e n и каждая из позиций S 1 , S 2 ,…, S n . Затем все элементы размещаются одновременно. Пусть дана матрица смежности С =║ С ij ║ n × n и матрица расстояний R =║ r ij || n × n . Для каждой строки матрицы смежности вычисляется оценка C i = ∑ = n C 1 j ij ( i = n1, ), а для каждой позиции − характеристика ∑ = = n r r 1j ij i ( i = n1, ) – сумма растояний от i -й позиции до остальных позиций. Очевидно, что позиции в центральной части коммутационного поля имеют меньшую характеристику r i , чем позиция на периферии платы. Поэтому естественно, что позиции в цен- тральной части наиболее благоприятны для размещения сильносвязанных эле- ментов. Размещение элементов е i ( i = n ,1 ) в позиции S j ( i = n ,1 ) представляет собой некоторую перестановку Р (1), Р (2),…, Р ( n ), где Р ( i ) – номер позиции, присвоен- ной i-му элементу. Рассмотрим векторы С =( С 1 , С 2 ,…, С n ) и r =( r 1 , r 2 ,…, r n ) и их скалярное произведение r c ∗ .