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

- 49 - Правило выбора позиции на плате для размещения элемента заключается в следующем. Выбранный для размещения элемент 0 j e должен быть установ- лен в одну из незанятых позиций. Эта позиция выбирается с учетом критерия размещения (например, минимум суммарной длины), но может быть предложен и другой способ выбора позиции. Обозначим r i ν – минимальное расстояние от позиции S i до одного из уже размещенных элементов в цепи V ν , связанной с элементом 0 i e . Тогда для раз- мещения элемента 0 i e выбирается такая позиция S i , для которой имеет место min Σ r i ν по всем цепям, соединяющим элемент 0 i e с уже размещенными, где ν – номер цепи или комплекса, кi V 0 – множество цепей, связывающих элемент 0 i e со всеми элементами е ∈ Е к . Матричные схемы выбора размещения Основой для выбора элемента е i и позиции s j на k- м шаге размещения может служить специальная матрица ( ) ( ) 1kn 1kn ij a A +− +− × = , где а ij представля- ет собой цену назначения элемента е i ∈ к Е в позицию s j ∈ к S при условии, что ( k -1)-й элемент уже размещен. Рассмотрим принцип максимина. Для каждой строки матрицы А опреде- ляется наименьший элемент ( ) n1, i amin a ij j 0ij = = . Для каждого столбца отыски- ваем наименьший элемент: ( ) n1, i amin a ij i j0i = = . Тогда ) a, (a min a j0i 0ij ji, 0j0i = . При использовании принципа минимального риска исходной информаци- ей также служит матрица А. Обозначим через a i разность между двумя наименьшими элементами в i- ой строке матрицы А , a j – разность между двумя элементами в j -м столбце.