Учебная САПР электронных средств. Асланянц В.Р. - 44 стр.

размеры контактных площадок и координаты их взаимного расположения,
а также тип выводов элемента: выводы планарные или штыревые.
      4. Результаты размещения элементов и РЦВУ.
      Выходные данные
      Список электрических соединений, в котором для каждого соедине-
ния определены координаты двух его концов, а так же номер цепи, "поро-
дившей" это соединение.
      Критерии качества
      Обычно это минимум суммарной длины соединений, т.е. строятся
кратчайшие соединения (соединения кратчайшей длины). В этой задаче
под длиной соединения понимается расстояние между его концами.
      Ограничения
      Если проектируется проводной монтаж, то может быть задано техно-
логическое ограничение на число проводников, которое разрешено при-
соединять к одному контакту.
      Математические модели
      Каждая электрическая цепь представляется полным графом, взве-
шенным по ребрам, который построен на контактах цепи. "Веса" ребер
означают расстояние между соответствующей парой контактов.
      В результате решения задачи для каждой цепи на полном графе оп-
ределяется дерево минимальной длины.
      Формализованная формулировка
      Для полного графа, взвешенного по ребрам, найти покрывающее де-
рево минимальной длины.
      Тип оптимизационной задачи
     Это частный очень простой случай задачи ЦЛП.
      Алгоритмы решения
     1. Алгоритм Прима.
     2. Алгоритм Краскала.
      Оба алгоритма дают точное решение, если строится обыкновенное
дерево (а не дерево Штейнера) и отсутствует указанное выше ограниче-
ние.
             5.2. Описание проектной задачи расслоения монтажа

     Термин "расслоение монтажа" означает распределение элементов
монтажа по слоям коммутационной платы.




                                                                    44