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

ПустьХ={х₁, х₂,…, х_n} – множество элементов, необходимое разместить во множество позиций L={l₁, l₂,…, l_n}. Дана матрица соединений R=||r_ij||_nxn и матрица расстоянийD=||d_ij||_nxn. На каждом шаге процесса один из не размещенных элементов помещается в одну незанятую позицию. В зависимости от правил выбора элемента и позиции на каждом шаге, существуют различные разновидности алгоритмов.

ПустьХ_k – элементы, размещенные до k-го шага, а L_k – позиции, занятые этими элементами; Х_k иL_k – соответственно неразмещенные элементы и незанятые позиции.

Выбор элемента. Любое правило выбора элемента для размещения основано на вычислении «меры связности» еще не размещенных элементов с уже размещенными. Естественной мерой связности двух элементов х_i и х_j является количество соединений между ними, заданное в матрице соединений R=||r_ij||_nxn.

Наиболее простой вариант выбора элемента. Для каждого неразмещенного элементах_iÎХ_k подсчитывается характеристика суммарной связности с уже размещенными элементами:

c_i = ∑r_ij,

х_jÎХ_k

Выбор в данном случае осуществляется на основании максимального значения характеристикиc_i. Т.е. выбирается элемент с максимальным количеством связей.

На каждом последующем шаге может использоваться другое правило выбора. Выбирается элементх_iÎХ_k, у которого максимальное число связей с размещенными элементами и минимальное число связей со свободными (c_i =max)

c_i = ∑r_ij - ∑r_ij.

х_jÎХ_k х_jÎХ_k

Данный выбор аналогичен принципу максимальной конъюнкции – минимальной дизъюнкции.

Выбор позиции. Выбранный для размещения элементх_i должен быть установлен в одну из свободных позиций (L_k). Эта позиция выбирается с учетом минимизации критерия размещения (например, критерий минимума суммарной длины соединений данного элементах_i с уже размещенными элементами Х_k). Рассматривается не все множество позицийL_k, а лишь те, которые находятся на периферии множества занятых позицийL_k (минимальное суммарное расстояние до занятых позиций определяется по матрицеD). На рисунке они отмечены знаком «+», занятые позиции – знаком «х».

		+	+
	+	r	r	+
	+	r	+
		+

 

Рис.6.3.1 Позиции для назначения

Перед началом размещения могут быть две ситуации:

· нет размещенных ранее элементов внешние выводы узла (контакты, разъемы и т.п.) не закреплены (в этом случае в алгоритме должен быть особо определен способ установки первого элемента);

· имеется группа заранее размещенных элементов или закрепленных выводов, тогда роль первого элемента выполняют закрепленные.

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

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