Последовательный алгоритм компоновки по связности

Основу метода составляет последовательная процедура выделения из исходной схемы связанных групп элементов.

Пусть дана схема соединений элементов из множества Х={х₁, х₂,…, х_n}. Требуется распределить элементы схемы по узлам (печатным платам) так, чтобы число элементов в каждом узле не превышало заданного числа r и число внешних связей каждого узла не превышало заданного числа m. Определим последовательный процесс назначения элементов в узлы T _s (s=1,…,γ), на каждом шаге выбирается один из нераспределенных элементов и приписывается очередному узлу. Выбранный элемент должен удовлетворять следующим условиям:

• включение его в формируемый узел обязано не нарушать ограничений по числу элементов и внешних связей;

• он должен иметь наибольшее число связей с элементами, уже помещенными в узел.

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

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

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

Формирование очередного узла начинается с выбора базового элемента х^* из множества не распределенных к этому моменту элементов (вначале все элементы, за исключением х₀, считаются нераспределенными). Процессом выбора базового элемента управляет функционал L₁, определенный на множестве нераспределенных элементов.

Функционал L₁(i) - число цепей, связывающих элемент х_i с оставшимися нераспределенными элементами. Базовым считается первый по порядку нераспределенный элемент х^*, для которого функционал L₁ принимает максимальное значение. Элемент х^* помещается первым и является как бы его центром, к которому в дальнейшем добавляются новые элементы числа нераспределенных.

Процессом дальнейшего формирования узла управляют два функционала L₂ и L₃, определенные на множестве нераспределенных элементов.

Функционал L₂(i) - число внешних цепей узла, полученного добавлением элемента х_i к формируемому узлу.

Функционал L₃(i) - число цепей, связывающих элемент х_i с элементами формируемого узла.

Выбор очередного элемента с помощью функционалов L₂ и L₃ производится следующим образом. Из свободных элементов выбирается элемент с минимальным значением L₂ (с минимальной дизъюнкцией) и помещают в узел. Если имеется несколько элементов с минимальным значением L₂, то для них вычисляется функционал L₃. В формируемый узел помещается тот, для которого L₃ имеет максимальное значение (максимальную дизъюнкцию).

Пример. Коммутационная схема:

Матрица комплексов:

Допустимое число внешних связей (m) =5; максимальное число элементов в узле (r)=3.

Результаты расчетов функционалов L₁, L₂ и L₃ и выбора отдельных элементов:

Сформированы два узла (T₁, T₂) с элементами х₁, х₂, х₃ и х₄, х₅, х₆.