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

- 52 - 8. Какое свойство скалярного произведения векторов используется в методе обратного размещения. . ЛЕКЦИЯ 11. Итерационные алгоритмы улучшения начального размещения Структура итерационных алгоритмов размещения аналогична итерацион- ному алгоритму компоновки. Для их применения необходимо иметь начальное размещение элементов, улучшение которого достигается перестановкой местами пар элементов, если такая перестановка уменьшает значение целевой функции в случае, когда за це- левую функцию берется суммарная длина связей. Если в качестве целевой функции выбирается наименьшее число соеди- нений, длина которых больше критической, то сначала ищут размещение, даю- щее минимум суммарной длины размещения, а затем осуществляют поиск та- ких пар элементов, длина связи между которыми оказывается больше критиче- ской. Для перестановки берут ту пару элементов, перестановка местами кото- рой приведет к ликвидации большего числа соединений с длиной, превышаю- щей критическую, и при этом не появятся новые соединения с длиной больше критической. Итерационные алгоритмы улучшения начального размещения использу- ют идеи метода последовательных приближений и являются комбинаторными аналогами градиентных методов оптимизации. В любом итерационном алгоритме исследуется некоторое подмножество размещений, в котором выделяются размещения с меньшим значением крите- рия качества, но при этом должно быть определено правило выбора размеще- ния.