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

- 45 - Например, попадание связанных между собой элементов в соседние по- зиции позволит быстрее найти минимум целевой функции. Пусть нужно установить элемент e j в случае, когда связанные с ним эле- менты уже находятся в установочных позициях. Свободные позиции нумеру- ются в порядке возрастания расстояния до позиций, уже занятых элементами, связанными с e j . Затем с помощью генератора случайных чисел осуществляется выбор позиции таким образом, чтобы наиболее вероятным было попадание элемента e j в позицию с наименьшим номером. Среди алгоритмов назначения различают алгоритм линейного назначения и алгоритм квадратичного назначения. Алгоритм линейного назначения базируется на алгоритме Штейнберга , суть которого заключается в следующем. Пусть имеется начальное размещение. Ш а г 1. В матрице смежности nnC С ij × = выделяем максимальное внутренне устойчивое подмножество элементов R i ( i =1,2,...). Ш а г 2. Из начального размещения исключаем элементы e i j ∈ R i и для них ищем такие позиции на плате из числа свободных, размещение в которые дает наименьшее значение целевой функции F ( x ). Ш а г 3. После нахождения оптимального размещения для элементов e i j ∈ R i ( j =1,2,…) находим максимальное внутреннее устойчивое подмножество для оставшихся неразмещенных элементов. Переходим ко второму шагу. Ш а г 4. Повторяем процедуру до тех пор, пока не будут размещены все элементы. Замечание . Эффективность алгоритма Штейнберга значительно зависит от числа нулей в матрице смежности. Алгоритм квадратичного назначения основан на использовании методов нелинейного программирования, в частности метода ветвей и границ. Эвристические методы размещения позволяют лучше учитывать кон- кретные конструкторско-технологические ограничения. Они подразделяются на