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

Пусть Х={х₁, х₂,…, х_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_{i j},

х_j Î Х_k

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

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

c_i = ∑ r_{i j} - ∑ r_{i j}.

х_j Î Х_k х_j Î Х_k

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

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

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

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

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

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

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

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