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

- 36 - продолжается до тех пор, пока не получим наилучший вариант компоновки первого куска. Из матрицы смежности удаляются строки и столбцы, соответствующие вершинам, вошедшим в первый кусок. Для оставшихся вершин вновь составля- ется матрица смежности и разрезается на два куска произвольным образом. Процедура повторяется так же, как при формировании первого куска. Процесс считается завершенным, когда будет сформирован ( ℓ –1)-й кусок. Обозначим через К 0 исходный вариант компоновки элементов, F 0 - значе- ние целевой функции, соответствующей этому варианту компоновки. Пусть исходному варианту К 0 соответствует множество узлов: T 1 , T 2 ,…, T i ,…, T j ,…, T n . Предположим, что произведен выбор пары элементов, ко- торые меняются местами. Это x i ∈ T i , x j ∈ T j . В этом случае мы получаем новый вариант разбиения К : T 1 , T 2 ,…, T i ′ ,…, T j ′ ,…, T n . Здесь T i ′ =( T i / x i ) ∪ x j , T j ′ =( T j / x j ) ∪ x i . Этому варианту соответствует значение целевой функции F 1. Рассматривая полученный вариант компоновки К 1 снова как исходный, можно осуществить поиск другой пары элементов, обмен которых приведет вновь к уменьшению значения целевой функции. Таким образом, в ходе итера- ционного процесса, заключающегося в перестановке пар элементов из одного куска в другой, образуется последовательность вариантов компоновки К 0 , К 1 , К 2 ,…, К s , которой отвечает монотонно убывающая последовательность значе- ний целевой функции F : F 0 > F 1 > … > F s . Тогда полученный на s -м шаге вариант компоновки будет отвечать ло- кальному минимуму целевой функции. Насколько он будет близок глобальному минимуму, зависит от тактики при выборе очередной пары элементов для пере- становки. Рассмотрим некоторые виды тактики перестановки. 1. Выбирается узел T i , а в нем произвольный элемент x z . Затем рассматри- ваются все возможные варианты обмена элемента x z ∈ T i с элементами x j ⊄ T i , т.е. вычисляются приращения ∆ F ( x z ,x j ). Для обмена выбирается тот элемент x l ,