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

1)   число межмодульных связей;

2)   число модулей разбиения.

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

2.1 Математическая постановка.

Электрическую схему удобно интерпретировать мультиграфом, тогда задача компоновки формулируется следующим образом: задан граф . Требуется разрезать его на отдельные куски , так, чтобы число ребер соединяющих эти куски было минимальным, то есть минимизировать  где - множество ребер соединяющих куски  и . При следующих ограничениях:

1)   на число кусков разрезания K;

2)   на число вершин в каждом из кусков;

3)   на число внешних связей каждого куска графа.

2.2 Алгоритмы решения.

Для задач невысокой размерности  применение нашли методы целочисленного программирования (метод ветвей и границ). Эти методы дают наиболее точный результат.

Для задач большей размерности эти методы неприемлемы из-за больших затрат времени и памяти ЭВМ, поэтому наибольшее распространение получили эвристические алгоритмы, которые можно разбить на две группы:

1)   последовательные алгоритмы;

2)   итерационные алгоритмы.

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

Итерационные алгоритмы в зависимости от исходных данных могут быть двух типов.

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

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