Автоматизация проектирования изделий электронной техники — страница 2

  • Просмотров 3882
  • Скачиваний 53
  • Размер файла 116
    Кб

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

назначения являются элементы не включенные в предыдущие узлы. Процесс заканчивается когда все элементы из множества E распределены. Исходные данные являются: -электрическая схема устройства. -максимально допустимое число элементов в модуле. Электрическую схему удобно представлять графом G=(E,V) , где множество вершин Е соответствует элементам эл-ой схемы, а множество ребер V –эл-ким связям между элементами. В таком виде задача

компоновки может быть сформулирована как задача разрезания графа G=(E,V) на множество подграфов Gr=(Er,Vr) ,где r=1,2,3…. В каждом подграфе число вершин соответственно Er должно не превосходить ранее заданного ограничения на число элементовов в узле К. Для любого разбиения должны выполняться следующие условия: (1) =; (2) (3) При проведении компоновки без учета ограничения на кол-во внешних выводов в узле все модули, кроме последнего, будут

иметь полное заполнение . и последнее условие примет вид (4) Пошаговое описание алгоритма. Шаг 1. Формирование очередного подграфа Gr(r=1,2,3…) начинается с выбора базовой вершины из множества нераспределенных вершин Ir . В начале процесса все вершины считаются нераспределенными, т.е. Ir=E.Критерием выбора вершины на роль базовой является ее степень () (под степенью вершины графа будем понимать кол-во ребер данного графа, инцидентных ей).

Выбор происходит в соответствии со следующим условием: (5) Базовая вершина будет первой по порядку вершиной подграфа Gr(Er,Vr), а оставшиеся вершины, принадлежащие множеству , являются кандидатами для включения в подграф Gr на последующих шагах алгоритма. Базовая вершина является, во-первых, как бы “центром” группирования, к которому прибавляются новые вершины, во-вторых, центром факторизации. Шаг 2. Из множества выделяется

подмножество Г() вершин, связанных с .Шаг 3. Для эл-та X введем функционал: L(x)= (6) определяющий число цепей , связывающих вершину X и вершины из множества Г и Ir\.Для упрощения записей будем отождествлять элемент (множество элементов).для формального вычисления функционала будем пользоваться формулой: (7) где -число связей между вершинами и . Шаг 4. Из всех вершин выбирается такая, у которой значение функционала минимально. Очевидно,что