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

- 57 - Тогда при смене местами пары е i ↔ e j имеем ∆ → → ↔ + = ) , (Δ) , (Δ) , ( i j j i j i eeF eeF eeF . Переставим местами ту пару элементов, для которой ∆ F будет наимень- шим. Итерационный алгоритм размещения, использующий медиану Суть алгоритма состоит в поиске циклической перестановки элементов на некоторой группе позиций, при которой улучшается значение целевой функ- ции. Такая перестановка называется эффективной. Наилучшая позиция называ- ется медианой. Выбор элементов, подлежащих перестановке, связан с определенными группами позиций. Так как итерационные алгоритмы применяются после неко- торого конструктивного алгоритма, то будем считать известным соответствие E → S . Рассмотрим принцип выбора из множества Е последовательности эле- ментов длиной k : π к = ( е 1 , е 2 ,…, е к ). С помощью датчика случайных чисел выби- рается элемент е 1 ∈ Е . Выбор следующего за е 1 элемента осуществляется таким образом: если перемещать некоторый элемент е 0 по позициям s ∈ S , оставляя неизменным закрепление остальных элементов, то можно для этого элемента е 0 найти наилучшую позицию s 0 , в которой целевая функция F примет наимень- шее значение F ( x 0 , y 0 )= ( ) ( ) yx, F min S yx, s ∈ = . Будем называть ε -окрестностью ( ) eO ε для элемента е множество раз- мерностью ε наилучших позиций этого элемента. Построим для элемента е 1 его ε O (e 1 ). Упорядочим элементы, попавшие в ε O ( e 1 ), по возрастанию значений целевой функции F . Первый из элементов в окрестности ε O ( e 1 ) возьмем в качестве e 2 в последовательности π к . Аналогично