Курсовая работа: Разработка печатного модуля РЭС с использованием учебных алгоритмов САПР
Успешное решение формализации конструкторской деятельности возможно лишь только при её алгоритмизации и автоматизации с использованием математических методов, теории графов, алгоритмов, математического программирования и исследование операции, методов вычислительной математики.
Следует отметить, что в общем случае процессы конструирования РЭА плохо поддаются формализации и с математической точки зрения относятся к так называемым плохо формализуемым задачам. Тем не менее для широкого круга задач удалось найти математическое описание и на его основе построить алгоритмы и программы их решения на ЭВМ.
В настоящее время на основе современных вычислительных комплексов и средств автоматизации созданы и находятся в промышленной эксплуатации схемы автоматизированного проектирования РЭА и ЭВА, позволяющие в значительной степени освободить конструктора-проектировщика от однообразной, трудоёмкой и утомительной умственной работы и повысить его интеллектуальные возможности на этапах принятия решений.
Существующие системы автоматизированного проектирования РЭА решают комплекс вопросов по проектированию схем и конструкций аппаратуры.
Нам необходимо разработать печатный модуль РЭС с использованием учебных алгоритмов САПР.
1. Решение задачи компоновки
1.1 Общее описание алгоритма
Общая схема процесса последовательной компоновки по связности имеет следующий вид:
Пусть дана схема соединения элементов из множества . Определим последовательный процесс назначения элементов в узлы Br( ) , на каждом шаге которого выбирается один из неразделенных элементов и приписывается очередному узлу.
Узел считается завершенным, если число элементов в узле равно заданному числу K.
После завершения очередного узла аналогичная процедура повторяется для следующего узла, причем кандидатами для назначения являются элементы, не включенные в предыдущие узлы. Процесс заканчивается, когда все элементы из множества E распределены.
Исходные данные являются:
– электрическая схема устройства (Рис.1);
– максимально допустимое число элементов в модуле.
Электрическую схему удобно представлять графом G=(E,V) , где множество вершин Е соответствует элементам электрической схемы, а множество ребер V –электрическим связям между элементами.
В таком виде задача компоновки может быть сформулирована как задача разрезания графа
G=(E,V) на множество подграфов
Gr = (Er, Vr),
где r=1, 2, 3….
В каждом подграфе число вершин соответственно Er должно не превосходить ранее заданного ограничения на число элементовв в узле К. Для любого разбиения должны выполняться следующие условия:
(1)
Рис.1
При проведении компоновки без учета ограничения на кол-во внешних выводов в узле все модули, кроме последнего, будут иметь полное заполнение и последнее условие примет вид
(2)
1.2 Пошаговое описание алгоритма
Шаг 1.
Формирование очередного подграфа Gr (r =1,2,3…) начинается с выбора базовой вершины из множества нераспределенных вершин Ir. В начале процесса все вершины считаются нераспределенными, т.е. Ir=E.
Критерием выбора вершины на роль базовой является ее степень ( ) (под степенью вершины графа будем понимать кол-во ребер данного графа, инцидентных ей). Выбор происходит в соответствии со следующим условием:
(3)
Базовая вершина будет первой по порядку вершиной подграфа Gr (Er,Vr), а оставшиеся вершины, принадлежащие множеству , являются кандидатами для включения в подграф Gr на последующих шагах алгоритма.
Базовая вершина является, во-первых, как бы “центром” группирования, к которому прибавляются новые вершины, во-вторых, центром факторизации.
Шаг 2.