Решение задачи компоновки конструктивных узлов

Постановка задачи разбиения электрических схем (компоновки)

Повторим материал из лекции 1.

При решении задач конструкторского проектирования можно условно выделить этапы:

ввод и контроль информации;

построение формальной модели схемы, т.е. разбиение электрической схемы на конструктивно законченные части - компоновка;

размещение;

трассировка;

выдача конструкторской документации.

Из всего комплекса задач технического проектирования самой важной является задача разбиения электрических схем на конструктивно законченные части.

Электрооборудование всегда содержит иерархию конструктивных частей.

При проектировании конструктивных узлов можно выделить уровни:

микросхема, электрорадиоэлемент, модуль;

типовой элемент замены (ТЭЗ) - включает в себя элементы уровня 1;

панель - состоит из типовых элементов замены;

рама - конструктивный уровень, в который входят панели;

стойки - собираются из элементов уровня 4, тумбы, пульты - собираются из элементов уровня 3.

Компоновкой (разбиением) электрической схемы на конструктивно законченные части называется процесс распределения элементов низшего конструктивного уровня в высший в соответствии с выбранным критерием.

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

Этот критерий принимается за основной, остальные включаются в ограничения.

Исходной для решения задачи компоновки ЭО является электрическая схема соединений. Для алгоритмизации и формального решения задачи производится переход от электрической схемы соединений ЭО к графу, мультиграфу, к гиперграфу одним из рассмотренных выше методов.

Вспомним определение.

Рис. 1 Рис. 2

электрический схема компановка алгоритм

Кусок графа G(Z,U) - это граф Q(X,Y), являющийся частью исходного графа такой, что X -- подмножество Z, а в Y входят все ребра из U, инцидентные X. Сформулируем задачу разбиения схемы как задачу разбиения графа G=(E, U) на куски Gi=(Ei,Ui), ЕiЕ, UiU, iI ={1,2,…,l}, где l - число кусков. Совокупность Р(G) называется разбиением графа G(E,U), если:

Другими словами: совокупность кусков Р(G)={G1…Gl} является разбиением графа, если:

любой кусок из этих совокупностей не пустой;

для любых двух кусков из Р(G) пересечение множества вершин пусто;

пересечение множества ребер может быть не пустым;

объединение всех кусков в точности равно исходному графу G.

Множество Uij определяет подмножество ребер Uij?U, попадающих в разрез между кусками Gi и Gj графа G.

На рис. 3.1, а приведен граф G, содержащий 8 вершин и 17 ребер. Одно из возможных разбиений графа G на три куска показано на рис. 3.1,б.

Обозначим ¦Uij¦= kij и назовем его числом соединительных ребер кусков Gi и Gj графов. Число соединительных ребер всех кусков графа

В рассмотренном примере К=12.

Задачей разбиения графа G(E,U) является нахождение такой совокупности частей, при которой число соединительных ребер графа удовлетворяло бы заданному критерию оптимальности.

Пусть граф G(E,U) разбит на l кусков G1, G2,…,Gl. Тогда множество ребер U графа G можно представить в виде:

Где

где:

Ui - подмножество всех ребер, инцидентных вершинам Ei куска Gi; Ui,i - подмножество ребер, соединяющих подмножество вершин Ei куска Gi между собой; Ui,j - подмножество ребер, соединяющих куски Gi и Gj.

Назовем коэффициентом разбиения ?(G) графа G отношение суммарного числа внутренних ребер (ребер подмножеств Ui,i ) к суммарному числу соединяющих ребер Ui,j.

Коэффициент ?(G) служит для оценки разбиения графа G на куски. Для графа на рис. 3.1 ?(G)=5/12.

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

Задача разбиения графа G на куски относится к задачам комбинаторно-логического типа, получение оптимального решения которых связано с большим перебором различных вариантов разбиения.

Алгоритмы разбиения графов

Существует большое количество алгоритмов разбиения графа, которые условно можно подразделять на следующие группы:

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

итерационные алгоритмы;

алгоритмы, основанные на приемах целочисленного программирования, например, на методе ветвей и границ;

алгоритмы, основанные на решении задачи о назначении;

смешанные алгоритмы.

Последовательные алгоритмы

Рассмотрим идеи последовательных алгоритмов. Пусть дана схема электрических связей из множества элементов Е={e1…en}. Будем последовательно назначать элементы eiE (i=1,n) в куски Gi i = 1,l. На каждом шаге выбирается один из нераспределенных элементов и помещается в очередной кусок.

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

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

Тактика назначения элементов в куски в самом общем виде следующая:

на очередном шаге выделяются те элементы, включение каждого из которых в кусок не нарушает ограничений по числу элементов и выводов узла;

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

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

Рассмотрим один из них.

Алгоритм 1 (последовательный алгоритм компоновки)

Пусть задан граф схемы G=(E,U), который необходимо разбить на l объектов G1,G2,…,Gl с числом вершин n1,n2,…,nl в кусках, ni=n, i=1,l.

формируем первый кусок. В графе выбирается вершина eiE с максимальной степенью (ei)=max. Если таких вершин несколько, то предпочтение отдается той вершине, которая имеет большее число кратных ребер, идущих к одной вершине. С вершины ei начинается построение куска G1;

в кусок G1 сначала включаем все вершины, смежные ei и саму эту вершину. Обозначим множество таких вершин Гei. Если количество вершин множества Гei равно n1, то кусок сформирован. Если число вершин больше n1, то удаляем «лишние» вершины, связанные с остающимися вершинами G меньшим числом ребер. Если мощность Гei меньше n1, то добавляем вершины из числа нераспределенных, имеющие наибольшее число связей с распределенными вершинами и наименьшее число связей с нераспределенными. Затем процесс повторяется для нового куска и т.д.

Описанный алгоритм достаточно прост и позволяет достаточно быстро получить результат. Однако, в общем случае он может привести к неэффективным результатам. Этот алгоритм наиболее эффективен для графа, в котором число вершин графа G значительно больше числа вершин в любом куске: n>>n1,n2,…,nl, поскольку существует много возможностей для выбора вершин.

Пример:

Пусть граф задан матрицей смежности

Требуется разбить граф G на три куска по 3, 2, 2 вершины, т.е. n1=3, n2=2, n3=3.

Выбираем вершину e5 с (e5) = 8. Тогда Гe5=e5,e3,e4,e6,e7.

n = 5 > n1=3. Нужно убрать 2 лишние вершины.

Для этого произведем условное удаление каждой вершины из Гe5 и подсчитаем число ребер zei, связывающих эту вершину с оставшимися вершинами Гe5.

При удалении e3 ze3=R35+R34+R36+R37=1+0+1+0=2

При удалении e4 ze4=R45+R34+R46+R47=1+0+4+0=5

При удалении e6 ze6=R65+R64+R36+R67=1+4+1+1=7

При удалении e7 ze7=R75+R74+R76+R73=5+0+1+0=6

Удаляем e3 (т.к. ze3 min) и получим Гe5=e5,e4,e6,e7

Нужно удалить еще одну вершину.

При удалении e4 ze4=R45+R46+R47=1+4+0=5

При удалении e6 ze6=R65+R64+R67=1+4+1=6

При удалении e7 ze7=R75+R74+R76=5+0+1=6

Удаляем e4 (т.к. ze4 = min) и получим Гe5=e5,e6,e7

Первый кусок сформирован. Из оставшихся вершин E*=e1,e2,e3,e4 формируем следующий кусок. Матрица смежности принимает вид.

Выбираем вершину e1 с (e1)=5. Тогда Гe1=e1,e2,e3.

n = 3 > n1=2. Нужно убрать 1 лишнюю вершину.

Для этого произведем условное удаление каждой вершины из Гe1 и подсчитаем число ребер zei, связывающих эту вершину с оставшимися вершинами Гe1.

При удалении e1 ze1=R12+R13=2 +3=5

При удалении e2 ze2=R21+R23=2+1=3

При удалении e3 ze3=R31+R32=3+1=4

Удаляем e2 (т.к. ze2 = min) и получим Гe1 = e1,e3

Гe1=(e1,e3) - кусок сформирован.

Т.к. остались всего две вершины, то третий кусок будет содержать вершины e2, и e4: Гe2=e2,e4.

Результат разбиения графа G на три куска: Гe5=e5,e6,e7, Гe1=e1,e3, Гe2=e2,e4.

Он приведен на рис. 3.2.

Число соединительных ребер всех кусков графа к равно 10.

Суммарное число внутренних ребер (ребер подмножеств Ui) равно 11.

Коэффициент разбиения G=11/10=1.1.

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

Провести разбиение по этому варианту самостоятельно и сравнить результаты.

Размещено на Allbest.ru