Последовательные алгоритмы компоновки
Суть последовательных алгоритмов заключается в том, что вначале по определенному признаку выбирают вершину или группу вершин, к которым затем присоединяют другие вершины графа для образования первого куска. Процесс повторяют до получения заданного разбиения.
1.2.1. Метод максимальной конъюнкции – минимальной дизъюнкции
Основной критерий разбиения графа на куски – минимум числа соединяющих ребер между кусками графа. Если формировать куски 
графа G так, чтобы каждый из кусков во множестве 
содержал возможно большее число ребер, то при этом получится локальный минимум суммарного числа K соединяющих ребер.
Рассмотрим метод максимальной конъюнкции – минимальной дизъюнкции [1, 4].
Пусть дана схема с множеством элементов 
, соединенных между собой множеством электрических цепей 
. Ее необходимо скомпоновать в узлы, включающие по t элементов. Число внешних связей узлов не должно превышать z (z – число контактов в разъеме).
Работа начинается с формирования 1-го узла. Первым выбирается элемент, подключенный к наибольшему числу цепей. Далее последовательно оцениваются по двум параметрам возможности назначения в формируемый узел оставшихся элементов.
Вначале отбирается множество элементов, назначение каждого из которых в формируемый узел не превышает предельно допустимого числа z внешних связей узла. Затем из полученного множества элементов выбираются такие, которые имеют с назначенными в формируемый узел элементами наибольшее число общих цепей.
При работе алгоритма схема представляется в виде графа Кенига 
, в котором подмножество вершин E и V интерпретируют соответственно множества элементов E и электрических цепей V. При этом вершина 
соединяется с вершиной 
ребром 
в том случае, когда элемент 
принадлежит цепи 
. Для вычисления на ЭВМ граф задается матрицей инцидентности 
, в которой число строк n определяется количеством элементов схемы, а столбцов m – количеством электрических цепей. Элемент 
, стоящий на пересечении i-й строки и j-го столбца, равен 1, если элемент подключен к цепи , и нулю в противном случае.
АЛГОРИТМ
1. Ввод матрицы 
.
2. По матрице определяем локальные степени вершин 
:
.
3. Из множества нераспределенных вершин E выбираем вершину с локальной степенью 
.
4. Назначаем выбранную вершину во множество 
, формируемого узла.
5. Строку 
матрицы , соответствующую назначенной вершине , модифицируем путем поразрядной дизъюнкции со строками матрицы, соответствующими нераспределенным элементам:
; 
;…
6. Определяем суммы элементов 
в модифицированных строках 
.
7. Из множества строк 
выбираем такие, в которых 
. Объединяем их во множество 
.
8. Если 
, то переходим к 17, иначе к 9.
9. Строку 
матрицы , соответствующую элементу , модифицируем путем поразрядной конъюнкции со строками множества :
;…
10. Определяем суммы 
элементов в модифицированных строках 
.
11. Из множества строк выбираем такую, в которой 
.
12. Вершину 
, дающую 
назначаем в формируемый узел 
.
13. Если 
, то идти к 17, иначе к 14.
14. Определяем множество нераспределенных элементов 
. Если 
, то идти к 19, иначе к 15.
15. Составляем матрицу 
. Для чего в исходной матрице вместо строк, соответствующих элементам, назначенным в узел 
, записываем дизъюнкцию всех указанных строк.
16. Идти к 5.
17. Узел считаем сформированным. Поэтому преобразуем матрицу . Исключаем из нее строки, соответствующие элементам, включенным в узел . Получаем матрицу 
.
18. Идти к 2.
19. Конец.
ПРИМЕР 2.1
Пусть дана схема соединений (рис. 2.1, а), которую необходимо скомпоновать в узлы, содержащие не более трех элементов 
, и каждый узел имеет не более пяти выводов 
.
Граф схемы представлен на рис. 2.1, б.
Решение
По матрице 
исходного графа определяем локальные степени вершин и приписываем их справа к каждой строке матрицы (число цепей, подключенных к каждому элементу схемы):
| ||||||||||||
| ||||||||||||
Максимальную локальную степень, равную трем, имеют вершины 
и 
. В качестве исходной выбираем 1-ю по порядку 
. (Процесс компоновки иллюстрируем таблицей 1.1). Выполним дизъюнкции 1-й строки 
, соответствующей , с остальными строками:
|
,
Рис. 2.1
|
и т. д.
Находим суммы элементов в дизъюнкциях: 
, 
, 
, 
, 
, 
и 
.
Выбираем вершины, имеющие 
, и включение которых в формируемый узел не превысит условия . Такими являются вершины 
, у которых 
.
Выполним конъюнкцию 1-й строки со строками отобранных элементов 
и 
:
|
,
|
и т. д.
Вычисляем суммы элементов в конъюнкциях 
, 
, 
и 
. Выбираем вершину 
, величина у которой максимальна, и включаем ее в узел 
.
Поскольку по условию в узел необходимо включить три элемента, то переходим к подбору следующей вершины.
Для этого модифицируем матрицу .
Вместо 1-й и 2-й строк в ней запишем дизъюнкцию этих строк.
Получим матрицу Q2:
| 
| 
| ||||||||||
|
| ||||||||||||
Снова вычисляем дизъюнкции строки 
со всеми остальными и определяем суммы элементов в них.
|
| |||||||||
|
,
|
| |||||||||
|
и т. д.
Результаты суммирований запишем справа от каждой строки матрицы 
. Минимальную 
имеют 
и 
. Причем 
. После выполнения конъюнкции строки с остальными строками и суммирования элементов в результирующих строках получим
|
| |||||||||
|
,
|
| |||||||||
|
и т. д.
Справа от матрицы запишем 
. Максимальное значение имеет вершина 
. Ее и включаем в узел 
: 
. Итак, узел сформирован, поскольку в него назначено три элемента. Число внешних связей у 
.
Аналогично формируем второй узел 
, рассматривая оставшиеся вершины 
. Для этого из исходной матрицы исключаем строки, соответствующие элементам 
. Получим:
| 
| 
| 
| ||||||||||
| 
| ||||||||||||
| 
| ||||||||||||
| 
| ||||||||||||
| 
| ||||||||||||
| 
|
После определения локальных степеней вершин первой в формируемый узел назначаем 
.
Вычисление дизъюнкции и конъюнкции строки 
, соответствующей , с остальными строками (см. 
) позволило назначить в узел элемент 
. Для назначения следующего элемента модифицируем :
| 
| 
| ||||||||||
| ||||||||||||
| 
| |||||||||||
| 
| |||||||||||
| 
| |||||||||||
| 
|
Нахождение дизъюнкций и конъюнкций 
с остальными позволило укомплектовать 
, 
.
Дальнейшее формирование узла 
происходит следующим образом.
Ef = E / T1 / T2 = {5, 6, 7}. Получаем матрицу:
|
| 
| 
| ||||||||||
| 
| ||||||||||||
| 
|
Максимальную локальную степень имеет 
, следовательно, 
. и у вершин 
и одинаковы, поэтому выбираем : 
. Наконец, в результате модификации имеем:
|
|
| ||||||||||
| ||||||||||||
| 
|
По результатам дизъюнкции и конъюнкции в узел распределен последний элемент: 
, 
.
Условия задачи выполнены. Схема скомпонована в узлы по три элемента и число внешних соединений каждого не превышает пяти (рис.2.1, в). Динамика процесса компоновки элементов в узлы представлена в таблице 2.1. Здесь n – номер формируемого узла, E – множество распределяемых на данном шаге элементов, 
– число подключённых к элементу цепей, ei – назначенный в узел элемент, Et – множество оставшихся элементов, c(qik) – число цепей, подключённых к i-му и k-му элементам (дизъюнкция), S(bik) – число цепей, соединяющих i-й и k-й элементы (конъюнкция), Tn – множество элементов назначенных в узел с номером n.
Граф схемы, разрезанный на три куска, приведён на рис. 2.2, а схема, скомпонованная в три блока – на рис. 2.3. Качество компоновки оценим по коэффициенту разбиения DG схемы.
Общее число цепей между блоками 
, число цепей внутри блоков 
.
Тогда коэффициент разбиения схемы 
.
Выводы
Достоинствами последовательных алгоритмов компоновки по связанности являются их простота реализации на ЭВМ и высокое быстродействие. Кроме этого, они позволяют легко учитывать дополнительные ограничения на компоновку: несовместимость отдельных элементов в узле, априорно заданное функциональное распределение некоторых элементов схемы и др.
Недостатком этих алгоритмов является локальный пошаговый характер оптимизации, приводящий к тому, что в начале процесса выделяются сильно связанные группы элементов, в то время как в последние узлы попадают мало связанные или вообще не связанные элементы. При жестких ограничениях на число выводов это приводит к увеличению числа узлов.
Поэтому эффективность таких алгоритмов выше при компоновке узлов с небольшим отношением числа элементов к числу выводов (печатных плат, панелей и т. д.). Кроме этого, результаты лучше для схем с относительно невысокой связанностью.
Таблица 2.1
| 
|
| 
| 
| 
|
| 
| 
|
|
|
|
|
|
|
|
|
|
| ||||||
|
|
|
|
|
| |||||||
|
|
|
|
| ||||||||
|
|
|
| |||||||||
|
|
|
| |||||||||
|
|
|
| |||||||||
|
|
|
| |||||||||
|
|
| ||||||||||
|
| |||||||||||
|
|
|
|
|
|
| ||||||
|
|
|
|
|
| |||||||
|
|
|
|
| ||||||||
|
|
|
| |||||||||
|
|
| ||||||||||
|
| |||||||||||
|
|
|
|
|
|
| ||||||
|
|
|
|
| ||||||||
|
|
|
Рис. 2.2
Рис. 2.3
ДОМАШНЕЕ ЗАДАНИЕ
2.1. Ознакомиться с методами решения задачи компоновки схем РЭС [1 – 5].
2.2. Изучить последовательный алгоритм компоновки (метод максимальной конъюнкции – минимальной дизъюнкции).
2.3. Подготовить данные для проведения эксперимента. Для этого полученный вариант схемы соединения конструктивных модулей представить математической моделью в виде графа Кёнига.
2.4. Предложить вариант компоновки «вручную» схемы по алгоритму.
3. ПОРЯДОК РАБОТЫ С ПРОГРАММОЙ «КОМПОНОВКА»
Алгоритм последовательной компоновки конструктивных элементов и узлов схем в узлы высшего уровня реализован в пакете учебной САПР PSAPRна ПЭВМ программой Pskomp – «Компоновка». Программа позволяет:
- компоновать элементы в блоки с минимизацией числа связей между блоками;
- учитывать число контактов в разъемах, устанавливаемых в блоках;
- назначать в блоки не больше заданного числа элементов;
- получать результат в графическом виде.
Для запуска программы «Компоновка» установить курсор на окно «Компоновка блока» (оно будет в зелёной рамке) и нажать Enter. Появится рабочее поле графического редактора «Компоновка» (см. рис.1.3.2 работы №1).
В верхней части экрана размещены слева направо следующие зоны:
- элементов. В ней указаны типы элементов, из которых можно набирать на рабочем поле схему электрическую принципиальную;
- информации о результатах работы программы. Номера формируемых модулей, максимально допустимое число элементов в них и число фактически назначенных элементов. Вначале в этой строке информация отсутствует. После получения результата компоновки схемы в ней выводятся сведения о количестве назначенных в каждый узел элементах.
- режим работы программы. В этой зоне выводится текущая информация о проектируемой схеме.
Справочная информация о работе с программой выводится на экран после нажатия клавиши F1 – Помощь (рис.2.4).
В центральной части экрана помещено дискретное рабочее поле, на котором набирается электрическая схема. Для её формирования надо установить красный прямоугольник (курсором или стрелками) в нужное место экрана и нажать клавишу Insert. На поле появится тот элемент, который в данный момент будет отображаться в левой верхней зоне. Смена типа элемента осуществляется нажатием серой клавиши « – » или щелчком ЛК мыши по элементу в верхней зоне (рис.2.5).
После того, как на поле установлены все элементы схемы, их необходимо соединить цепями. Для этого надо перейти в режим ввода цепей – нажать на серую клавишу «*» или указать на неё курсором и щелкнуть ЛК.
Вместо красного прямоугольника на рабочем поле появится «+». Для соединения контактов элементов цепью необходимо установить + на край 1-го контакта и нажать клавишу Insert. На краю контакта появится красная точка. Затем перемещать курсор ко 2-му контакту. При этом на каждом изгибе цепи нажимать широкую клавишу «Пробел» и будет появляться прямолинейный фрагмент строящейся цепи. После завершения цепи дважды нажать клавишу «Пробел». На 2-м контакте также появится красная точка. Это признак построения цепи (рис.2.5).
В нижней части экрана размещена строка с указаниями клавиш и названий основных команд редактора.
Кроме этого система позволяет загружать схему, соответствующую результатам покрытия (предыдущей работы). Для этого надо нажать одновременно клавиши Alt + F3. На экран будет выведена схема (рис.2.5).
Рис.2.4
Рис.2.5
Зададим условия компоновки. Назначим в узлы по три элемента, а разъем зададим из пяти контактов. Для этого в верхней строке экрана для 1-го и 2-го узлов зададим по 3 элемента. Надо нажимать на клавишу 1 до тех пор, пока не появится тройка, затем также на клавишу цифры 2, либо, установив на них курсор, щёлкать ЛК мыши до тех пор, пока не установится цифра 3. Для установки числа контактов в разъеме нажимать на клавишу буквы «z» или щёлкать курсором по цифре «Максимальное число внешних связей». Установить число 5 (рис.2.6).
Рис.2.6
После того как схема сформирована, можно приступать к решению задачи компоновки. Для этого надо нажать клавишу Enter. По запросу системы выбрать ручной режим. После этого на экране появятся исходные данные для расчета (рис.2.7): сверху слева матрица инцидентности, справа – сумма элементов в строках, дизъюнкция, конъюнкция и номера строк. Снизу пояснения и результаты работы алгоритма. Нажатием клавиши Enter можно по шагам выполнить весь расчёт. Результаты будут выведены на экран (рис.2.8).
Повторное нажатие на клавишу Enter выводит на экран результат компоновки элементов исходной схемы в блоки (рис.2.9).
Рис.2.7
Рис.2.8
Рис.2.9