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

- 55 - где c ij – элементы матрицы смежности nn ij С C × = . Введем множество перестановочных матриц { X }: nn ik x X × = , для кото- рых       = = случае. противном в 0 позиции в находится если ,1 , ik k i ik x s е x В данных матрицах номер строки – это номер элемента, а номер столбца – это номер позиции. Сформулируем задачу размещения следующим образом. Найти перестановочную матрицу, для которой имеет место : jh ik kh ij xxrb ji, X XF max }{ min ) ( 0 = . Тогда для улучшения начального размещения можно предложить сле- дующий алгоритм парных перестановок . 1. Найти элемент e i со связью максимальной длины. 2. Найти другой элемент e j такой, что перестановка пары e i и e j местами уменьшает число связей максимальной длины и не приводит к образованию еще более длинных связей. Таких элементов может быть больше одного. 3. Среди всех элементов e j , отобранных во втором пункте, выбрать та- кой элемент e j* , что перестановка пары e i ↔ e j* ликвидирует наибольшее число связей максимальной длины. Осуществить такую перестановку. 4. Повторять п.п. 1 − 3 до тех пор, пока либо не исчезнут все связи максимальной длины (в этом случае переход к п. 5), либо ни одна из допусти- мых перестановок не уменьшит число связей максимальной длины. В этом слу- чае конец работы алгоритма. 5. Рассмотреть следующую по длине наибольшую связь и перейти к п. 1.