Алгоритмы последовательного размещения по связности.

Относятся к классу конструктивных алгоритмов начального размещения. Для них характерен учет меры связности. Дано: электрическая схема из n конструктивных элементов и n позиций на коммутационном монтажном поле. Реализация: n-шаговый процесс, на каждом шаге определяется очередной элемент из неразмещенных, а затем определяется место для размещение данного элемента. Расположение зафиксированных элементов не меняется. Выбор элемента и позиции - операции, не связанные между собой, то есть можно вначале выбрать элементы, а затем - позиции. Исходные данные и обозначения:
E = {e₁,..., e_n} - множество конструктивных элементов; L = {l₁,..., l_n} - множество позиций
E_k - элементы, размещенные до k-го шага, а L_k - позиции, занятые этими элементами.

I. Выбор элемента
1. По наибольшему числу связей с одним из уже размещенных элементов (алгоритм попарных связей): C_i = max r_ij, e_i ∉ E_k, e_j ∈ E_k
 , где J_ij – мн-во цепей, связывающих элементы i и j, ρ_s - размер цепи, λ ≥ -1 – весовой коэффициент, который позволяет учесть вклад цепей той или иной размерности в общую оценку, ω_s ∈ (0, 1] - поправочный коэффициент, позволяющий учесть особенности отдельных цепей. Выбирается элемент с максимальным C_i.
2. По наибольшей связности с уже размещенными элементами C_i = Σ r_ij, e_i ∉ E_k, e_j ∈ E_k
3. С учетом связей с уже размещенными и еще не размещенными элементами
C_i = Σ r_ia - Σ r_ib, e_i ∉ E_k, e_a ∈ E_k, e_b ∉ E_k
4. По относительной связности C_i = Σ r_ia / Σ r_ib, e_i ∉ E_k, e_a ∈ E_k, e_b ∉ E_k
Преимущества: простота алгоритмов, быстрота получения элементов.

II. Выбор позиции
Рассматриваются позиции, соседние с уже размещенными элементами, например:

 (здесь x - уже размещенные элементы, v - оцениваемые позиции-кандидаты)
Пусть L - множество незанятых позиций-кандидатов, а его элементы - l_γ. Элемент, для которого ищется позиция - e_i.

Способы оценки позиции:
1. F_γ = Σ(e_j ∈ E_k) r_ijd_γj, где d_γj - расстояние между оцениваемой позицией и j-м элементом ® оцениваются только смежные с занятыми позиции
2. Пусть d_γ^S - минимальное расстояние до цепи S, связывающей элемент с уже размещенным. F_γ = Σ(S ∈ J_ik) d_γ^S, где J_ik - множество всех цепей между уже размещенным элементом k и размещаемым.
3. (для ортогональных соединений) оценка производится по полупериметру минимального прямоугольника, охватывающего элементы, соединенных одной цепью. F_γ = Σ(S ∈ J_ik) [(x^s_max - x^s_min) + (y^s_max - y^s_min)]
Замечания:
1. В случае, когда несколько позиций имеют одинаковую оценку, выбор происходит по взвешенным оценкам каждой позиции. Ищется "центр тяжести": x_i = Σ(e_j ∈ E_k) r_ijx_j / Σ(e_j ∈ E_k) r_ij & y_i = Σ(e_j ∈ E_k) r_ijy_j / Σ(e_j ∈ E_k) r_ij
Выбирается позиция, наиболее близкая к центру тяжести.
2. Первый элемент выбирается по наибольшему числу связей с остальными элементами. Выбранный элемент желательно размещать в центре монтажного поля. Например, можно использовать матрицу расстояний D = ||d_ij||_nxn, определяющую расстояния от каждой позиции до всех остальных. Место для первого эл-та можно определить как min{d_i}: d_i = Σ(j:1..n) d_ij.

Метод связывания пар.

Алгоритм:
1. Рассчитываем матрицу соединений R = ||r_ij||_nxn. r_ij = Σ(s ∈ J_ij) ω_s(ρ_s + λ) / ρ_s, где J_ij - множество цепей, связывающих элементы i и j, ρ_s - размер цепи, λ ≥ -1 - весовой коэффициент, который позволяет учесть вклад цепей той или иной размерности в общую оценку, ω_s ∈ (0, 1] - поправочный коэффициент, позволяющий учесть особенности отдельных цепей.
2. Выбирается пара элементов с max r_ij. Эти два элемента устанавливаются в центр монтажного поля.
3. Выбирается пара элементов с max r_ij такие, что e_i ∉ E_k, e_j ∈ E_k. Этот (i-й) элемент размещается в позицию, наиболее близкую к j-му элементу. Если несколько позиций равноценны, то определяется центр тяжести:
x_i = Σ(e_j ∈ E_k) r_ijx_j / Σ(e_j ∈ E_k) r_ij
y_i = Σ(e_j ∈ E_k) r_ijy_j / Σ(e_j ∈ E_k) r_ij
Выбирается позиция, наиболее близкая к центру тяжести. Повторять пункт 3, пока все модули не размещены.

Пример: ρ1=5; ρ2=4; ρ3=3. λ=-1, Wj=1

 1.RAB = (5-1)/5=0,8 RBE = (5-1)/5 + (4-1)/4 =1,55 (цепь1 + цепь2)

2. Выбираем максимум из матрицы (1,55)это B и E

3.Размещаем их в центр

4.В строчках B и E находим наибольшее значение (1,42) (D)

5. Элемент D должен быть ближе всего к В (тк из строчки В) таких позиций 3

7. Находи центр масс для размещённых:

8. Находим макс из неразмещённых (смотрим неразмещённые столбцы) При равенстве выбираем первый. И т д.       

координата  , где 2 и 3 – координаты соответственно B и E; координата, но вся строка 2 занята ® возможные варианты: 1 либо 3. Пусть будет 3.