Этап 1. Выбор элемента

Любое правило выбора элемента связано с вычислением меры связности еще неразмещенных элементов с размещенными. Связность элементов определяется матрицей смежности R=||r_ij||_n*n. Приведем несколько способов выбора элемента:

1. для каждого неразмещенного элемента e_i выбирается C_i

Ci=max rij, eiEk, ejEk

(8.4)

и среди этих неразмещенных элементов для размещения выбирается элемент с наибольшим числом связей с уже размещенными элементами, т.е. e_i* такой, что C_i*=max C_i, e_i*E_k;

2. для каждого неразмещенного элемента подсчитывается C_i

(8.5)

т.е. для каждого неразмещенного элемента e_iE_k вычисляется суммарная связность с уже размещенными элементами;

3. для каждого неразмещенного элемента e_i подсчитывается C_i

(8.6)

т.е. оценивается число связей очередного размещаемого элемента с уже размещенными и неразмещенными и выбирается элемент с максимальным значением C_i;

4. для каждого неразмещенного элемента e_i подсчитывается C_i

(8.7)

т.е. оценивается отношение числа связей между размещенными и неразмещенными элементами и выбирается элемент с максимальным значением C_i.

При выборе очередного элемента для размещения естественно рассматривать лишь те элементы, которые связаны с уже размещенными элементами.

Используемое правило выбора может привести к нескольким элементам – кандидатам для размещения. В этом случае либо размещается любой из них, например, с меньшим номером, либо окончательный выбор среди этих элементов осуществляется с использованием другой характеристики.

Все рассмотренные характеристики не зависят от положений элементов, поэтому в принципе может быть выполнено предварительное упорядочение всех элементов, а потом уже и их размещение.

Этап 2. Выбор позиции

Выбранный элемент размещается в одной из незанятых позиций из множества L_k. Эта позиция выбирается с учетом минимизации выбранного критерия, в частности, минимума суммарной длины связей. Естественно, что при последовательном процессе размещения может быть оценена лишь суммарная длина частичных монтажных соединений данного элемента с уже размещенными.

В принципе возможен подход, когда при установке элемента в позицию рассчитываются трассы соответствующих соединений. Длина этих соединений является критерием для выбора позиции. Однако длительное время расчета на компьютере делает этот подход нереальным, по крайней мере, при конструировании узлов с печатными соединениями, и ограниченно применимым при конструировании монтажных схем проводных соединений.

Учитывая эти замечания, для оценки длин монтажных соединений применяются приближенные методы.

Рассмотрим некоторые из критериев:

1. Вычисляется

(8.8)

где d_sp(j) – расстояние между позицией s (в которую размещается i-й элемент) и позицией p, в которой уже стоит j-й элемент. Выбирается та из позиций, l_sL_k, для которой значение F_s минимально т.е. F_s* =min F_s, l_sL_k.

Д ля экономии вычислений всегда целесообразно рассчитывать не все множество позиций L_k, а лишь часть, находящуюся на периферии множества занятых позиций L_k (см. рис. 8.1).

2. Вычисляется

(8.9)

(сумма по цепям) где:

• V(i,E_k) - множество цепей, связывающих размещаемый элемент е_i c элементами E_k;

• d_s^q – минимальное расстояние позиции l_s до одного из уже размещенных элементов в цепи V_qV, связанной с элементом е_i.

Позиция выбирается по минимуму F_s.

3. Если используется ортогональная матрица, то вычисляется

(8.10)

Позиция выбирается по минимуму F_s.