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

перграф. В отличие от задачи покрытия здесь веса вершин имеют другой
смысл: это например площадь, занимаемая элементами в монтажном поле.
Другой пример – это мощность теплоотдачи элемента.
     Формализованная формулировка задачи
     В терминах введенных ММ разбиения схем сводится к разбиению
гиперграфа, взвешенного по вершинам, на подграфы, для которых указаны
ограничения на суммарный вес их вершин и число внешних гиперребер.
     Сведение к задаче математического программирования
     Разбиение схем ЭС можно свести к задаче дискретного нелинейного
программирования (ДНП).
     Алгоритмы решения
     1. Метод ветвей и границ.
     2. Последовательные алгоритмы.
     3. Итерационные алгоритмы.
     4. Дихотомические алгоритмы.

                     3.3. Описание программы DECOM-3

      В лабораторной работе исследуется последовательный алгоритм раз-
биения схем. Схема программы DECOM-3 представлена на рис. 1.
      Входные данные
      E - количество элементов схемы;
      Н - число электрических цепей схемы;
      V - число внешних цепей схемы;
      B - число выводов элемента;
      G - максимальная вместимость узла;
      W - максимальное число внешних выводов узла;
      CB (E, B) - список цепей схемы. Например, СВ17, 9 = 37 означает, что к
9-му выводу 17-го элемента присоединена 37-я цепь;
      GE (E) - вес элементов (принимает значения 1, 2, ... ). Например, если
GE17 = 1, а GE41 = 4, то это означает, что для 41-го элемента потребуется
площадь в 4 раза большая, чем для 17-го;
      CV(V) - список внешних цепей схемы.




                                                                         17