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

      Такими элементами монтажа (объектами расслоения) могут быть
следующие четыре :
        1. Подсхемы.
        2. Электрические цепи.
        3. Электрические соединения.
        4. Трассы (расслоение после прокладки трасс).
      В учебной САПР CROCUS-3 объектами расслоения являются элек-
трические соединения.
      Входные данные
        1. Список соединений.
        2. Число коммутационных слоев платы.
      Выходные данные
      Вектор (кортеж) распределения соединений по слоям платы.
      Критерии качества
          1. Минимальная степень конфликтности между элементами мон-
тажа в каждом слое. Под конфликтом понимается потенциальное пересе-
чение проводников.
          2. Минимальное число межслойных переходов.
          3. Минимальное число слоев платы (если оно не задано в качест-
ве ограничения).
      Математические модели
      Граф конфликтов.
      Формализованная формулировка
      Выполнить раскраску графа конфликтов заданным количеством
цветов, минимизируя число конфликтных ребер.
      Тип оптимизационной задачи
      Экстремальная задача комбинаторного типа.
      Алгоритмы решения
          1. Метод Магу [12].
          2. Итерационные алгоритмы ( один из них рассмотрен в данном
разделе).

        5.3. Описание проектной задачи упорядочения соединений
     Большинство алгоритмов прокладки трасс используют последова-
тельную стратегию: трассы прокладываются поочередно.
     Упорядочение соединений (может быть и цепей) заключается в оп-




                                                                      45